• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q32E

Expert-verified
Found in: Page 536

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

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

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

See the step by step solution

## Step 1: Define the Recursive formula

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

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

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

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

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