Recursion Trees and Asymptotic Complexity: T(n) = T(n/3) + T(n/2) + n

Question

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.

Answer 1

As a hint, use the formula for the sum of a geometric series:

1 + (5 / 6) + (5 / 6)² + (5 / 6)³ + ... = 1 / (1 - 5/6) = 6

Hope this helps!

Answer 2

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)