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

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.$$

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 )$$.

• Hi Steven! How did you find p? I calculated as: $-p(\log 2 + log 3) = 1 ==> p = -1/(log 2 + log 3) =-2.30$ – user777 May 9 '20 at 13:40
• Careful! $\log(a+b)$ is not $\log(a)+\log(b)$. I don't think there is an easy analytical solution. The function $2^{-p} + 3^{-p}$ is decreasing with $p$ and for $p=0$ it evaluates to $2$ while for $p=1$ it evaluates to $\frac{5}{6}<1$ so you can approximate it numerically using bisection. Alternatively you can use Newton's method to find the root of $2^{-p} + 3^{-p} -1$ or you can consider the Taylor series centered in $p=0$: $1+\sum_{i=1}^\infty\frac{(-\ln 2)^i+(-\ln 3)^i}{i!}\cdot x^i$. If you truncate it to polynomials of degrees 3 and 4 you can narrow the range of $p$ to $(0.764, 0.793)$. – Steven May 9 '20 at 14:41