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}\]
- What is the value of \(f(5)\)?
The recursion depth of \(f(n)\) is defined 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)\).
- 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}\]
What is \(g(5)\)?
What is \(g(2^k)\), where \(k \ge 0\) is an integer? Briefly explain your answer.
What is \(g(2^l+2^k)\), where \(l> k \ge 0\) are integers? Briefly explain your answers.
Explain briefly why the value of \(g(n)\) is equal to the recursion depth of \(f(n)\).
