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

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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