Question

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

Short answer

The required result is\(f(n) = O\left( {{n^{{{\log }_4}5}}} \right)\).

Step-by-step solution

Explain the Master theorem

The master theorem is a formula for solving recurrence relations of the form: \({\bf{T}}({\bf{n}}) = {\bf{aT}}({\bf{n}}/{\bf{b}}) + {\bf{f}}({\bf{n}})\),where \({\bf{n}} = \)the size of the input \({\bf{a}} = \)number of sub-problems is in the recursion \({\rm{n}}/{\rm{b}} = \)size of each sub-problem. All subproblems are assumed to have the same size.

Apply Master Theorem

Consistent with the notation given:

\(a = 5,b = 4,c = 6,d = 1\)

This means that\({b^d} = 4 < 5 = a\).

Hence\(f(n) = O\left( {{n^{{{\log }_4}5}}} \right)\).