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

Suggested languages for you:

Americas

Europe

Q22E

Expert-verified
Found in: Page 535

### Discrete Mathematics and its Applications

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

# Suppose that the function ${f}$ satisfies the recurrence relation ${\mathbit{f}}{\mathbf{\left(}}{\mathbit{n}}{\mathbf{\right)}}{\mathbf{=}}{\mathbf{2}}{\mathbit{f}}{\mathbf{\left(}}\sqrt{\mathbf{n}}{\mathbf{\right)}}{\mathbf{+}}{\mathbit{l}}{\mathbit{o}}{\mathbit{g}}{\mathbf{ }}{\mathbit{n}}$ whenever ${\mathbit{n}}$ is a perfect square greater than ${\mathbf{1}}$and ${\mathbit{f}}{\mathbf{\left(}}{\mathbf{2}}{\mathbf{\right)}}{\mathbf{}}{\mathbf{=}}{\mathbf{}}{\mathbf{1}}$.a) Find ${\mathbit{f}}{\mathbf{\left(}}{\mathbf{16}}{\mathbf{\right)}}$.b) Give a big -${\mathbit{O}}$estimate for${\mathbit{f}}{\mathbf{\left(}}{\mathbit{n}}{\mathbf{\right)}}$. [Hint: Make the substitution ${\mathbit{m}}{\mathbf{=}}{\mathbit{l}}{\mathbit{o}}{\mathbit{g}}{\mathbit{n}}$].

(a) The required function $f\left(16\right)=12$.

(b) The required function $f\left(n\right)=O\left(\mathrm{log}n\mathrm{loglog}n\right)$.

See the step by step solution

## Step 1: Given information

The function$f$satisfies the recurrence relation $f\left(n\right)=2f\left(\sqrt{n}\right)+1$, Where $n$is a perfect square greater than$1$and$f\left(2\right)=1$.

## Step 2: Explain the Master theorem

The master theorem is a formula for solving recurrence relations of the form: ${\mathbf{T}}{\mathbf{\left(}}{\mathbf{n}}{\mathbf{\right)}}{\mathbf{=}}{\mathbf{aT}}{\mathbf{\left(}}{\mathbf{n}}{\mathbf{/}}{\mathbf{b}}{\mathbf{\right)}}{\mathbf{+}}{\mathbf{f}}{\mathbf{\left(}}{\mathbf{n}}{\mathbf{\right)}}$, where ${\mathbf{n}}{\mathbf{=}}$ the size of the input ${\mathbf{a}}{\mathbf{=}}$ number of sub-problems is in the recursion ${\mathbf{n}}{\mathbf{/}}{\mathbf{b}}{\mathbf{=}}$size of each subproblem. All subproblems are assumed to have the same size.

## Step 3: Calculate the functionf(16)

(a)

To find $f\left(16\right)$:

$f\left(16\right)=2f\left(4\right)+\mathrm{log}\left(16\right)$

$f\left(16\right)=2\left(2f\left(2\right)+\mathrm{log}\left(4\right)\right)+\mathrm{log}\left(16\right)$

$\begin{array}{c}f\left(16\right)=2\left(2+2\right)+4\\ f\left(16\right)=12\end{array}$

## Step 4: Calculate the value off(n)by the Master theorem

(b)

Use the suggested substitution and let $m=\mathrm{log}n$.

So,${2}^{m}=n$

Now, it will may be $f\left(n\right)=f\left({2}^{m}\right)$.

$\begin{array}{l}f\left(n\right)=2f\left(\sqrt{{2}^{m}}\right)+\mathrm{log}\left({2}^{m}\right)\\ f\left(n\right)=2f\left({2}^{m/2}\right)+m\end{array}$

Rewrite the function, for clarity, as $g\left(m\right)=f\left({2}^{m}\right)$.

And so,$g\left(m\right)=2g\left(m/2\right)+m$ .

Next, apply the Master theorem with $a=2, b=2, c=1, d=1$:

$g\left(m\right)=O\left(m{\mathrm{log}}_{2}m\right)$

Hence, $f\left(n\right)=O\left(\mathrm{log}n\mathrm{loglog}n\right)$