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{d}}\mathbf{\right)}$.

Short answer

The expression$f\left(n\right)=O\left(n^d\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.

Prove the expression f(n) is O(nd).

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

Now given $a<b^d$.

So,${\log }_{b}a<d$.

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