Question

Give a big- $\mathit{O}$estimate for the function $\mathit{f}$in Exercise$\mathbf{34}$if$\mathit{f}$is an increasing function.

Short answer

The required result is $f\left(n\right)=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:$\mathbf{T}\left(\mathbf{n}\right)=\mathbf{aT}(\mathbf{n}/\mathbf{b})+\mathbf{f}\left(\mathbf{n}\right)$,where $\mathbf{n}=$the size of the input $\mathbf{a}=$numberof sub-problems is in the recursionsize 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\left(n\right)=O\left(n^{lo{g}_{4}5}\right)$.