7
$\begingroup$

I'm looking at the reccurrence $$T(n) = T(n/2) + T(n/3) + n,$$ which describes the running time of some unspecified algorithm (base cases are not supplied).

Using induction, I found that $T(n) = O(n\log n)$, but have been told that this is not tight. Indeed, assume inductively that $T(k) \leq Ck\log k$ for all $k<n$ (and sufficiently large values of $k$), then

\begin{align*} T(n)&\leq C\frac{n}{2}\log\frac{n}{2} + C\frac{n}{3}\log \frac{n}{3} + n\\ &= C\frac{5}{6}n\log n - n(C/2+C\log3/3 - 1). \end{align*}

Now I choose $C$ large enough for $(C/2+C\log3/3 - 1) > 0$, and so the last expression is dominated by $C\frac{5}{6}n\log n\leq Cn\log n$.

My first question is, what is a tighter bound that this?

Second, I tried to use the Akra-Bazzi method to solve this, so let $p$ solve $$\left(\frac{1}{2}\right)^p + \left(\frac{1}{3}\right)^p = 1.$$ Then approximately $p=0.79$, and (with $g(n) = n$) I get $$\int_1^n \frac{g(u)}{u^{p+1}} du = \int_1^n \frac{1}{u^{p}} du = \frac{1}{1-p}(n^{1-p}-1),$$ and so

$$T(n) = \Theta\left(n^p\left(1+\frac{1}{1-p}(n^{1-p}-1)\right)\right).$$

This equals $\Theta(n^p + \frac{1}{1-p}n-\frac{1}{1-p}n^p)$, so overall $\Theta(n)$, since $p<1$. My second question is that I don't really believe that $T$ is linear, so what went wrong in my application of Akra-Bazzi?

Best regards.

$\endgroup$
5
$\begingroup$

If $T(1)\le 6$ and $T(2)\le 12$, we can show that $T(n)\le 6n$ by induction.

$$T(n) = T(n/2) + T(n/3) + n \le 6(n/2)+ 6(n/3)+n= 6n.$$

More generally, let $c\gt6$ be a constant such that $T(1)\le c$ and $T(2)\le 2c$, then we can prove routinely that $T(n)\le cn$. Although it might seem unbelievable to you, it is true that $$T(n)=O(n).$$

Intuitively, since $\dfrac12+\dfrac13\lt1$, the terms $T(n/2)$ and $T(n/3)$ is not big enough to lift $n$ to a power of $n$ of a larger exponent.

There is nothing wrong in your application of Akra-Bazzi method, which tells us that $T(n)=\Theta(n)$.

$\endgroup$
4
$\begingroup$

Let $S(n) = T(n)/n$. Then $S(n)$ satisfies the recurrence $$ S(n) \leq \frac{1}{2} S\left(\frac{n}{2}\right) + \frac{1}{3} S\left(\frac{n}{3}\right) + 1. $$ In particular, if $C$ satisfies $$ \frac{1}{2} C + \frac{1}{3} C + 1 \leq C $$ then $S(n/2),S(n/3) \leq C$ would imply $S(n) \leq C$. This is the case for all $C \geq 6$.

$\endgroup$

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.