# Recurrence of T(n) = T(n/3) + T(2n/3)

I've searched online for this but I only seem to find answers for a similar equation:

T(n) = T(n/3) + T(2n/3) + cn


But the one I'm trying to solve is:

T(n) = T(n/3) + T(2n/3)


Base case: We can assume T(a) = Theta(1) for any constant a.

I've succeeded in proving (by induction) that T(n) = O(n*log(n)). I thought the answer should be Theta(n*log(n)), but I cannot prove that T(n) = Omega(n*log(n)).

So my question is - am I correct that the answer is O(n*log(n)), and NOT Theta(n*log(n))? IF that's true that would really be great...

If I'm wrong I will of course explain where I'm stuck in the induction process...

Thanks!

P.S. If you need to, please try to explain using induction, because I haven't learned all methods for solving these problems yet.

• Hmmm, the most simple solution is $T(n)=n$ - but as you are not searching for this you might have some additional special constraints in your mind? – Gottfried Helms Mar 19 '14 at 15:40

umm, if you have solution for $cn$ take $c=0$? Why waste time?

• It doesn't always works nicely: most asymptotic techniques assume $c > 0$ and discard low-order terms by making approximations. If $c=0$, the leading term vanishes and the approximations do not hold anymore. – Clement C. Mar 19 '14 at 15:18
• Then can the OP link to whatever he was talking about? Or at least tell us what it is? – cderwin Mar 19 '14 at 15:18
• @ClementC. even if the leading term vanishes, $\mathcal O(f(x))$ holds. the $\Omega$ fails. as did here. – Guy Mar 19 '14 at 15:19
• Yes -- but the analysis leading to the solution $\Theta_c(n\log n)$ may most likely no longer be valid (the constants in the $\Theta$ depend on $c$). So the $O()$ holds, but the proof does not... – Clement C. Mar 19 '14 at 15:22
• @ClementC. actually it does hold. If $c=0$, then our new T is strictly less than the old T. quite easily done. – Guy Mar 19 '14 at 15:23

Without the additive term, the (exact) solution will be of the form $T(n)=\alpha n$ for some constant $\alpha$ depending on the first terms. By substitution (or induction if you prefer): $$T(n) = T\left(\frac{n}{3}\right)+T\left(\frac{2n}{3}\right) = \alpha \frac{n}{3}+\alpha \frac{2n}{3} = \alpha n$$

• in case you are calculating, might wanna make that $\lfloor \frac{n}{3} \rfloor$. – Guy Mar 19 '14 at 15:21

The other answers are simpler, but if you want to see how to use induction to prove the results from definitions:

$$T \in \Theta(g)$$

is defined as:

$$(\exists k_1 > 0,\, \exists k_2 > 0,\, \exists n_0,\,\forall n > n_0)\\ g(n)k_1 \le T(n) \le g(n)k_2$$

which means that $T$ is bounded above and below by scalar multiples of $g$ for sufficiently large $n$. You've already done the hard part, which is choosing a $g$, so we just use induction to find some $k_1$, $k_2$, $n_0$. We will see that there actually aren't any though.

$$n\,\log(n)k_1 \le T(n) \le n\,\log(n) k_2$$

$$n\,\log(n)k_1 \le T(n/3) + T(2n/3) \le n\,\log(n) k_2$$

For the lower bound, we steal the strong inductive assumptions that $\frac n3\, \log(\frac n3)k_1 \le T(n/3)$ and $\frac {2n}3\, \log(\frac {2n}3)k_1 \le T(2n/3)$ to get :

$$n\,\log(n)k_1 \le \frac n3\, \log(\frac n3)k_1 + \frac {2n}3\, \log(\frac {2n}3)k_1$$

which simplifies to

$$3n\,\log(n) \le n\, \log(n) + 2n\, \log(n) -n\,\log(3)-2n\log(1.5)$$

$$n\,\log(3)+2n\log(1.5) \le 0$$

...which means that you can't satisfy the lower bound, your function isn't growing as fast as $n\,\log\,n$.

We can try Clement C. answer:

$$\alpha\,n\,k_1 \le T(n/3) + T(2n/3) \le \alpha\,n\,k_2$$

By inductive assumptions:

$$\alpha\,n\,k_1 \le \alpha\,n/3\,k_1 + \alpha 2n/3 \,k_1 \land\\ \alpha\,n/3\,k_2 + \alpha 2n/3 \,k_2 \le \alpha\,n\,k_2$$

It is easy to see that any choice of $k_1$ and $k_2$ satisfy the bounds, so Clement C. answer holds for all values of $\alpha$: $$(\forall \alpha)\, T \in \Theta(\alpha n)$$

• Thanks. I also used induction and could get the O part right, but I thought I was doing some kind of silly mistake when I saw I can't get the Omega part.. but at least this time I did OK. Thanks for the detailed explanation. – Cauthon Mar 19 '14 at 21:50