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.

  • 1
    $\begingroup$ The solution is not $\Theta(n\log n)$. $\endgroup$ – FrankW Mar 19 '14 at 14:52
  • 1
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Mar 19 '14 at 17:21
  • $\begingroup$ Keep trying. You're on the right path; you just need to keep trying and put in some more effort, and you'll get there. See if you can guess some other candidate solutions and use guess-and-check to verify them. If you're really stuck, you can also try solving this for a few simple cases (e.g., what if $T(1)=1$, $T(2)=1$, $T(3)=1$; graph some of the values of $T$; what do you find?). You can solve this problem using the techniques in our reference question. I'm going to vote to mark this as a dup of that question. $\endgroup$ – D.W. Mar 19 '14 at 21:34

Hint: Suppose that $T(m) \leq Cm$ for all $m < n$, and that $n$ is divisible by $3$. Then $$ T(n) = T(n/3) + T(2n/3) \leq C(n/3) + C(2n/3) = Cn. $$ Use this to obtain a good bound on $T(n)$ when $n$ is a power of $3$.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.