# The recursion $T(n) = T(n/2)+T(n/3)+n$

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

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