How to solve the recurrence T(n) = T(n/2) + T(n/4)

问题:

I tried recursion tree method since the master method is not applicable for this recurrence but it seems that it is not the right method also, any help would be appreciated !

回答1:

Either I have an error somewhere in my derivation or there is an error in your statement.

---

You do this by unrolling the recursion:

T(n) = T(n/2) + T(n/4) = 2T(n/4) + T(n/8) 
T(n) = 3T(n/8) + 2T(n/16)
T(n) = 5T(n/16) + 3T(n/32)
....
T(n) = F(i + 1)T(n/2^(i-1)) + F(i)T(n/2^i)

where F(i) if a Fibonacci number.

Using boundary condition T(n/2^i) = T(1) have n = 2^i -> i = log2(n).

T(n) = F(log2(n) + 1) T(2) + F(log2(n)) T(1) which is equal F(log2(n) + 1)

Now using this formula:

and stripping it to only phi^n (square root of 5 has nothing to do with complexity and the second thi^n -> 0 if n->inf) you will get:

T(n) = phi^(log2(n)+1) = phi * phi^log2(n) which is equal to O(n^log2(phi)), where log2(phi) = 0.694.

P.S. Look at it as a hint or a suggestion. Now you do not need college or a professor to learn something. Determination and perseverance is more important. Do not be afraid to try doing something. You already asked this question and claimed to try master method where you failed. People suggested you a completely different approach and here you claim that you tried completely the sam and have not tried the method that worked in a previous case.