Question

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

Short answer

\({\rm{O}}\left( {{n^{0.63}}} \right)\)

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

Master theorem is directly applicable here with\({\rm{a}} = 2,\;{\rm{b}} = 3,{\rm{c}} = 4\), and\({\rm{a}} = 2,\;{\rm{b}} = 3,{\rm{c}} = 4\) \({\rm{d}} = 0\). Since \(a > {b^d}\), we have that \({\rm{f}}({\rm{n}})\) is\({\rm{O}}\left( {{n^{{{\log }_b}a}}} \right) = {\rm{O}}\left( {{n^{{{\log }_3}2}}} \right)\~{\rm{O}}\left( {{n^{~0.63}}} \right)\).