Please help me with this problem

[Student 100]

I have this problem and I have no Idea how to solve it.

Q-" solve the following recurrence relation. (Assume n=2k ")


F(n)= { 1 n=2 ;
2 f(n/2) + (n-1) n>2 ;

please help me with anything

[jemidiah]

Unroll the sum for a few terms. I've written it suggestively for the first few:

f(n) = 2 f(n/2) + (n-1) = 2 2 f(n/4) + 2(n/2-1) + n-1 = 2^2 f(n/2^2) + 2n - 2-1 ...

From there you should be able to guess an answer, eventually. Just make sure you check it since there are a lot of places to mess up and drop a term.