Hi, I have attached the question as a word file. I have worked through it, but do not have solutions. These are my answers:
i) 32
ii) 4
iii) 4
I am not sure about iv, v and vi, my thoughts are:
iv) answer = k + 1
g(2^k) = 1 + g(2^(k-1))
.
.
= k + g(1)
= k+1 + g(0)
v) answer = l + 2
g(2^l + 2^k) = 1 + g(2^l-1 + 2^k-1)
.
.
= k + g(2^l-k + 2^0)
= k+1 + g(2^l-k)
.
.
= l+1 + g(2^l-l)
= l+2 + g(0)
vi) recursion depth of g(n) is same as its value, since if it takes A steps to reach g(0), 1 is added A times.
f(n) has same recursion depth as g(n), as the same operations are used to simply it. Since value of g(n) = recursion depth of g(n)
then recursion depth of f(n) = value of g(n)
Thank you