How to find a good asymptotic approximation of T(n) = T(n/2) + T(n/3) + 1?

Question

I can't figure out how to find a good asymptotic approximation for the following recurrence relation: $$T(n) = T(n/2) + T(n/3) + 1.$$

Answer 1

You can write your recurrence as $$ T(n) = \sum_{i=1}^k a_i T(b_i x + h_i(n)) + g(n) $$ with:

• $k=2$
• $a_1 = a_2 = 1$
• $b_1 = \frac{1}{2}$, and $b_2 = \frac{1}{3}$
• $h_1(n) = h_2(n) = 0$
• $g(n) = 1$

From Akra–Bazzi theorem, the solution to your recurrence is $T(n) = \Theta\Big( n^p \big(1 + f(n)\big)\Big)$, where $p$ is such that $a_1 b_1^p + a_2 b_2^p =1$ and $f(n) = \int_1^n \frac{1}{u^{p+1}} \text{d} u$.

Substituting, we have $2^{-p} + 3^{-p} = 1$, which shows that $0.78 < p < 0.79$.

Therefore: $$ f(n) = \int_1^n \frac{1}{u^{p+1}} \text{d} u \le \int_1^\infty \frac{1}{u^{p+1}} \text{d} u = \frac{1}{p} = \Theta(1), $$

and the solution to your recurrence is $T(n) = \Theta( n^p )$.