As a hint, use the formula for the sum of a geometric series:
1 + (5 / 6) + (5 / 6)2 + (5 / 6)3 + ... = 1 / (1 - 5/6) = 6
Hope this helps!
Frage
I'm trying to use recursion trees to find the asymptotic complexity of this function:
T(n) = T(n/3) + T(n/2) + n if n > 5; otherwise T(n) = 1
I've made the recursion tree and determined that each level has _(5/6)^k * n_ complexity at each level. From here I'm not sure how to proceed. I know I have to figure out the complexity of the depth but aren't really sure how to do that.
Keine korrekte Lösung
Andere Tipps
As a hint, use the formula for the sum of a geometric series:
1 + (5 / 6) + (5 / 6)2 + (5 / 6)3 + ... = 1 / (1 - 5/6) = 6
Hope this helps!
These type of recursion can be easily solved using Akra-Bazzi method. In your case a1=a2=1
, b1 = 1/3
, b2=1/2
and g(n) = n
.
Solving 1/3^p + 1/2^p = 1
your p=0.7878
. Now you have to solve an integral and you are done.
This is dominated by x
and therefore your complexity is O(n)