2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Hi Steven! How did you find p? I calculated as: $-p(\log 2 + log 3) = 1 ==> p = -1/(log 2 + log 3) =-2.30 $ $\endgroup$ – user777 May 9 '20 at 13:40
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Steven May 9 '20 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.