Review question

Can we show $g(n)$ is equal to the recursion depth of $f(n)$? Add to your resource collection Remove from your resource collection Add notes to this resource View your notes for this resource

Ref: R7507

Question

Let $f(n)$ be a function defined, for any integer $n \ge0$, as follows: $f(n)= \begin{cases} 1 & \text{if n=0,}\\ (f(n/2))^2 & \text{if n>0 and n even,}\\ 2f(n-1) & \text{if n>0 and n odd.} \end{cases}$

1. What is the value of $f(5)$?

The recursion depth of $f(n)$ is deﬁned to be the number of other integers $m$ such that the value of $f(m)$ is calculated whilst computing the value of $f(n).$ For example, the recursion depth of $f(4)$ is $3$, because the values of $f(2)$, $f(1)$, and $f(0)$ need to be calculated on the way to computing the value of $f(4)$.

1. What is the recursion depth of $f(5)$?

Now let $g(n)$ be a function, defined for all integers $n \ge 0$, as follows: $g(n)= \begin{cases} 0 & \text{if } n=0,\\ 1+g(n/2) & \text{if n>0 and n is even,}\\ 1+g(n-1) & \text{if n>0 and n is odd.} \end{cases}$

1. What is $g(5)$?

2. What is $g(2^k)$, where $k \ge 0$ is an integer? Briefly explain your answer.

3. What is $g(2^l+2^k)$, where $l> k \ge 0$ are integers? Briefly explain your answers.

4. Explain briefly why the value of $g(n)$ is equal to the recursion depth of $f(n)$.