1

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.

Cauthon
  • 389
  • 3
  • 16
  • 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

3 Answers3

4

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

Guy
  • 8,857
  • 1
  • 28
  • 57
  • 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
  • 1
    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
  • 1
    @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
  • For the $O()$, indeed -- my bad. All I was saying that if the result gives $\Theta(f(n))$ for any $c>0$ while hiding the dependence on the constant $c>0$ (as pretty much always), just plugging $c=0$ would still "say" $\Theta(f(n))$ -- while this is not true. – Clement C. Mar 19 '14 at 15:25
  • Thanks, I didn't think I could just take C=0 exactly because what was stated here - i.e. that C>0. But anyway I understand that I didn't make a mistake - the correct answer is O(nlogn), which is good :) thanks! – Cauthon Mar 19 '14 at 15:26
  • @user2996797 you're welcome. :) – Guy Mar 19 '14 at 15:30
1

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

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

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

DanielV
  • 23,556
  • 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