Suggested languages for you:

Americas

Europe

Q10E

Expert-verifiedFound in: Page 535

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**Find ${\mathit{f}}{\mathbf{\left(}}{\mathit{n}}{\mathbf{\right)}}$ when ${\mathit{n}}{\mathbf{=}}{{\mathbf{2}}}^{{\mathbf{k}}}$, where ${\mathit{f}}$ satisfies the recurrence relation ${\mathit{f}}{\mathbf{\left(}}{\mathit{n}}{\mathbf{\right)}}{\mathbf{=}}{\mathit{f}}{\mathbf{(}}{\mathit{n}}{\mathbf{/}}{\mathbf{2}}{\mathbf{)}}{\mathbf{+}}{\mathbf{1}}$with ${\mathit{f}}{\mathbf{\left(}}{\mathbf{1}}{\mathbf{\right)}}{\mathbf{=}}{\mathbf{1}}$.**

Thus, $n={2}^{k}$ is equivalent with $k={\mathrm{log}}_{2}n$.

**A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms: ${\mathbf{\text{f(n) = a f(n / b) + c}}}$**

Given information are $n={2}^{k},f\left(n\right)=f(n/2)+1\u200a\text{and}\u200af\left(1\right)=1$

Repeatedly apply the recurrence relation:

$f\left(n\right)=f\left({2}^{k}\right)\phantom{\rule{0ex}{0ex}}f\left(n\right)=f\left({2}^{k-1}\right)+1\phantom{\rule{0ex}{0ex}}f\left(n\right)=f\left({2}^{k-2}\right)+2\phantom{\rule{0ex}{0ex}}f\left(n\right)=\dots \phantom{\rule{0ex}{0ex}}f\left(n\right)=f\left({2}^{2}\right)+(k-2)\phantom{\rule{0ex}{0ex}}f\left(n\right)=f\left({2}^{1}\right)+(k-1)\phantom{\rule{0ex}{0ex}}f\left(n\right)=f\left({2}^{0}\right)+k\phantom{\rule{0ex}{0ex}}f\left(n\right)=f\left(1\right)+k\phantom{\rule{0ex}{0ex}}f\left(n\right)=1+k\phantom{\rule{0ex}{0ex}}f\left(n\right)=k+1\phantom{\rule{0ex}{0ex}}f\left(n\right)={\mathrm{log}}_{2}n+1\phantom{\rule{0ex}{0ex}}$

Therefore, $n={2}^{k}$ is equivalent with $k={\mathrm{log}}_{2}n$.

94% of StudySmarter users get better grades.

Sign up for free