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


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

  • $\begingroup$ 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? $\endgroup$ – Gottfried Helms Mar 19 '14 at 15:40

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

  • $\begingroup$ 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. $\endgroup$ – Clement C. Mar 19 '14 at 15:18
  • 1
    $\begingroup$ Then can the OP link to whatever he was talking about? Or at least tell us what it is? $\endgroup$ – cderwin Mar 19 '14 at 15:18
  • $\begingroup$ @ClementC. even if the leading term vanishes, $\mathcal O(f(x))$ holds. the $\Omega$ fails. as did here. $\endgroup$ – Guy Mar 19 '14 at 15:19
  • $\begingroup$ 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... $\endgroup$ – Clement C. Mar 19 '14 at 15:22
  • 1
    $\begingroup$ @ClementC. actually it does hold. If $c=0$, then our new T is strictly less than the old T. quite easily done. $\endgroup$ – 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$$

  • $\begingroup$ in case you are calculating, might wanna make that $\lfloor \frac{n}{3} \rfloor$. $\endgroup$ – 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)$$

  • $\begingroup$ 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. $\endgroup$ – Cauthon Mar 19 '14 at 21:50

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.