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