# Thread: Divide an conquer algorithms

1. ## Divide an conquer algorithms

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

I'm very confused by this theory any help would be appreciated. I was using f(n)= C1*n^(logb(a)) +C2
where C1 = f(1) + c/(a-1) and C2 = -c/(a-1)

but a =1 im very confused

2. For this problem, it is easier to look at some special cases and use common sense than to fiddle with a general formula. So write a table with three rows. The first row contains $k=0,1,2,3,4,\dots$, the second row lists $n=2^k$ and the third row lists $f(n)=f(2^k)$. Then look at how to express values in the third row in terms of the first two rows. Or the other way around. E.g., if you find that $g(f(n))=n$ for some function $g$ that has an inverse $g^{-1}$, then $f(n)=g^{-1}(n)$.

3. You give:
f(n) = f(n/2) + 1 with f(1)=1.

So:
f(1)=1
f(2)=f(1)+1=1+1=2
f(4)=f(2)+1=2+1=3
f(8)=f(4)+1=3+1=4
etc.