Question

Use Exercise 31 to show that if $\mathit{a}\mathbf{<}{\mathit{b}}^{\mathbf{d}}$, then$\mathit{f}\mathbf{\left(}\mathit{n}\mathbf{\right)}$is$\mathit{O}\mathbf{\left(}{\mathit{n}}^{{\mathbf{log}}_{{\mathbf{b}}^{\mathbf{a}}}}\mathbf{\right)}$.

Short answer

The expression $f\left(n\right)=O\left(n^d\log n\right)$ is proved.

Step-by-step solution

Define the Recursive formula

A recursive formula is a formula that defines any term of a sequence in terms of its preceding terms.

Solve by recursive procedure on f(n)

From exercise 31 , for $a\ne b^{\mathrm{d}}$and n is a power of b, then $f\left(n\right)=C_1{n}^{\mathrm{d}}+C_2{n}^{{\log }_{{\mathrm{b}}^{\mathrm{a}}}}$for constants $C_1$and$C_2$.

Now given$a>b^{\mathrm{d}}$.

So,$lo{g}_{\mathrm{b}}a>d$.

This gives$f\left(n\right)=C_1{n}^{\mathrm{d}}+C_2{n}^{{\log }_{{\mathrm{b}}^{\mathrm{a}}}}<(C_1+C_2)n^{{\log }_{{\mathrm{b}}^{\mathrm{a}}}}\in O\left(n^{{\log }_{{\mathrm{b}}^{\mathrm{a}}}}\right)$