Question

Use Exercise 29 to show that if $\mathit{a}\mathbf{=}{\mathit{b}}^{\mathbf{d}}$, then $\mathit{f}\mathbf{\left(}\mathit{n}\mathbf{\right)}$is $\mathit{O}\mathbf{(}{\mathit{n}}^{\mathbf{d}}\mathbf{}\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{n}\mathbf{)}$.

Short answer

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

Step-by-step solution

Define 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 .

It is easy to see that since $f\left(n\right)=n^{d}f\left(1\right)+c{n}^d{\log }_{b}n$, by exercise 29, we have $f\left(n\right)=O\left(n^d\log n\right)$.

This is because $f\left(1\right)$and $c$are constants and $n^d\log n$grows faster than$n^d$.