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.
Best Answer
umm, if you have solution for $cn$ take $c=0$? Why waste time?