T(n) = T(n/2) + T(n/4) + O(1), what is T(n)?

Question

How to solve this recurrence: T(n) = T(n/2) + T(n/4) + O(1)

It doesn't seem like Master Method will help, as this is not in the form of T(n) = aT(n/b) + f(n). And I got stuck for quite a while.

Answer 1

Akra Bazzi is a much more powerful method than Master method.

Since the 'non-recursive' term is O(1), it amounts to solving the equation

1/2^p + 1/4^p = 1

And the answer you get will be T(n) = Theta(n^p)

I believe solving the above (quadratic in 1/2^p) gives us p = log_2 phi where phi is the golden ratio.

Computing that gives us T(n) = Theta(n^0.694...)