StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q32E

Expert-verifiedFound in: Page 536

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

** 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)}}$.**

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

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

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}^{{\mathrm{log}}_{{b}^{a}}}$ for constants ${C}_{1}$and ${C}_{2}$.

Now given $a<{b}^{d}$.

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

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

94% of StudySmarter users get better grades.

Sign up for free