Question

Show that the algorithm from Exercise \({24}\) has worst-case time complexity \({O}\left( {{log n}} \right)\)in terms of the number of comparisons.

Short answer

The notation is

\(\begin{array}{l}O\left( {{n^d}\log n} \right)\\ = O\left( {{n^0}\log n} \right)\\ = O(\log n)\end{array}\)

And proved that, the time complexity will be \(O(\log n)\).

Step-by-step solution

Given data

Result previous exercise

\(f(n) = f(n/2) + 1\)

Definition

In the analysis of algorithms, the master theorem for divide-and-conquer recurrences provides an asymptotic analysis (using Big O notation) for recurrence.

Simplify the O notation

Result previous exercise

\(f(n) = f(n/2) + 1\)

Master theorem when \(f(n) = af(n/b) + c{n^d}\), then

\(f(n) = \left\{ {\begin{array}{*{20}{c}}{O\left( {{n^d}} \right),}&{\:{\rm{if}}\:a < {b^d}}\\{O\left( {{n^d}\log n} \right),}&{\:{\rm{if}}\:a = {b^d}}\\{O\left( {{n^{{{\log }_b}a}}} \right),}&{\:{\rm{if}}\:a > {b^d}}\\a&{ = 1}\\b&{ = 2}\\c&{ = 1}\\d&{ = 0}\end{array}} \right.\)

In this case, \(a = 1\)

and \({b^d} = {2^0} = 1\).

Thus, we need to use \(a = {b^d}\) :

\(\begin{array}{l}O\left( {{n^d}\log n} \right)\\ = O\left( {{n^0}\log n} \right)\\ = O(\log n)\end{array}\)

Hence proved that, the time complexity will be \(O(\log n)\).