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

Q22E

Expert-verifiedFound in: Page 535

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**Suppose that the function ${f}$**** satisfies the recurrence relation ${\mathit{f}}{\mathbf{\left(}}{\mathit{n}}{\mathbf{\right)}}{\mathbf{=}}{\mathbf{2}}{\mathit{f}}{\mathbf{\left(}}\sqrt{\mathbf{n}}{\mathbf{\right)}}{\mathbf{+}}{\mathit{l}}{\mathit{o}}{\mathit{g}}{\mathbf{\u200a}}{\mathit{n}}$ **** whenever ${\mathit{n}}$**** is a perfect square greater than ${\mathbf{1}}$****and ${\mathit{f}}{\mathbf{\left(}}{\mathbf{2}}{\mathbf{\right)}}{\mathbf{}}{\mathbf{=}}{\mathbf{}}{\mathbf{1}}$****.**

**a) Find ${\mathit{f}}{\mathbf{\left(}}{\mathbf{16}}{\mathbf{\right)}}$****.**

**b) Give a big -${\mathit{O}}$****estimate for${\mathit{f}}{\mathbf{\left(}}{\mathit{n}}{\mathbf{\right)}}$****. [Hint: Make the substitution ${\mathit{m}}{\mathbf{=}}{\mathit{l}}{\mathit{o}}{\mathit{g}}{\mathit{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)$.

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

**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{(}}{\mathbf{n}}{\mathbf{/}}{\mathbf{b}}{\mathbf{)}}{\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.**

(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\right(2)+\mathrm{log}(4\left)\right)+\mathrm{log}\left(16\right)$

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

(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(m/2)+m$ .

Next, apply the Master theorem with $a=2,\u200a\u200ab=2,\u200a\u200ac=1,\u200a\u200ad=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)$

94% of StudySmarter users get better grades.

Sign up for free