# 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 $\displaystyle k=0,1,2,3,4,\dots$, the second row lists $\displaystyle n=2^k$ and the third row lists $\displaystyle 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 $\displaystyle g(f(n))=n$ for some function $\displaystyle g$ that has an inverse $\displaystyle g^{-1}$, then $\displaystyle 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.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}