Question

Give a big-\(O\) estimate for the function \(f\) in Exercise \(10\) if\(f\) is an increasing function.

Short answer

\(O(\log n)\)

Step-by-step solution

Master Theorem definition

In MASTER THEOREM, let\(f\)be an increasing function that satisfies the recurrence relation\(f(n) = af(n/b) + c{n^d}\)whenever\(n = {b^k}\), where\(k\)is a positive integer,\(a \ge 1,b\)is an integer greater than\(1\), and\(c\)and\(d\)are real numbers with\(c\)positive and\(d\)nonnegative. Then\(f(n)\)is\(O\left( {{n^d}} \right)\)if\(a < {b^d}{\rm{ }}O\left( {{n^d}\log n} \right)\)if\(a = {b^d}\)and \(O\left( {{n^{{{\log }_b}a}}} \right)\)if\(a > {b^d}\).

Apply Master Theorem

Apply Master theorem with \(a = 1,b = 2,c = 1\), and \(d = 0\). Here \(a = {b^d}\), we have that \(f(n)\) is \(O\left( {{n^d}{\mathop{\rm logn}\nolimits} } \right) = O(\log n)\)..