Question

Find f(n) when n = 2k , where f satisfies the recurrence relation f(n) = f(n/2) + 1 with f(1) = 1.

Answer 1

Given $n=2^k$. The function f is defined using the recursive relation $f(n)=f(n/2)+1$. Using the recursion we can write,

$f(n/2)=f(n/2^2)+1\\</p><p>f(n/2^2)=f(n/2^3)+1$

So we can write,

$f(n)=f(n/2)+1\\</p><p>f(n)=f(n/2^2)+1+1\\</p><p>f(n)=f(n/2^3)+1+1+1\\</p><p>..............................\\</p><p>f(n)=f(n/2^k)+k$

When $n=2^k$, the above function becomes,

$f(2^k)=f(2^k/2^k)+k\\</p><p>f(2^k)=f(1)+k\\</p><p>f(2^k)=1+k$

Thus $f(n)=k+1$