T(n) = T(n/2) + T(n/4) + O(1), what is T(n)?
-
13-11-2019 - |
سؤال
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.
المحلول
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...)
لا تنتمي إلى StackOverflow