Question

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

Short answer

The expression\(f(n) = O\left( {{n^{{{\log }_b}a}}} \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^d}\) and\(n\)is a power of\(b\), then \(f(n) = {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(n) = {C_1}{n^d} + {C_2}{n^{{{\log }_b}a}} < \left( {{C_1} + {C_2}} \right){n^{{{\log }_b}a}} \in O\left( {{n^{{{\log }_b}a}}} \right)\)