1
$\begingroup$

I made a recurrence tree and guessed that solution to $T(n)=2T(n-2)+n$ is $O(2^{n/2})$ and I am now trying to prove this through substitution. These are my steps so far, but I can't get it to pass for some reason:

\begin{align} T(n-2) &\leq c2^{(n-2)/2}\\ T(n) &= 2(c2^{(n-2)/2})+n\\ &\leq c2^{n/2} \quad (?) \end{align}

But as far as I see, it can never add up, because it will always be greater than the $+n$ term and times $2$. Any help will be much appreciated.

$\endgroup$
10
  • 1
    $\begingroup$ The same recurrence relation is/has been discussed here, so maybe you can glean something from that. $\endgroup$ May 5 '14 at 13:00
  • $\begingroup$ Yes I looked at that, but didn't really help, since he's trying to prove another bound $\endgroup$
    – manis
    May 5 '14 at 13:14
  • $\begingroup$ One of the answers proves the bound that you are after (well, he uses Big Theta, which is a stronger bound). $\endgroup$ May 5 '14 at 13:17
  • $\begingroup$ No he doesn't prove the bound by induction, he just expands the recurrence to generate a guess $\endgroup$
    – manis
    May 5 '14 at 13:20
  • 1
    $\begingroup$ @manis In math you're allowed to do everything which is logically valid to prove whatever it is you want to prove. In this case you were instructed to use a particular proof method, but outside the realm of exercises this is never the case. Real math is not as mechanical as you've been taught to expect. $\endgroup$ May 5 '14 at 14:30
1
$\begingroup$

The hints you've been given almost work. The important idea is that your guess, $T(n)≤c2^{n/2}$, while correct, doesn't behave nicely in your induction proof, as you noted. What's the problem? Clearly, it's that "$+n$" term in the recurrence, so let's try to make it work by choosing a better guess: $$ T(n)≤c2^{n/2}−kn \quad\text{for some suitable } k $$

With this guess, we'll have $$\begin{align} T(n)&=2T(n−2)+n\\ &\le 2(c2^{(n−2)/2}−k(n−2))+n\\ &=c2^{n/2}−2k(n−2)+n\\ &=c2^{n/2}−2kn+4k+n \end{align}$$ and if we can find a suitable $k$ to make this less than or equal to $c2^{n/2}−kn$ we'll be done. In other words, we need to find $k$ such that $$ −2kn+4k+n≤kn $$ It's not hard to see that this will happen if $$ k\ge\frac{n}{n−4} $$ and this will be satisfied when $k=5$ for any integer $n>4$. Now go back to the inductive proof and recast it for the guess $T(n)\le c2^{n/2}−5n$. You'll find that everything works nicely. Finally, observe that $c2^{n/2}−5n=O(2^{n/2})$ and you'll be done.

This is explained in a bit more detail in this answer to a similar question.

$\endgroup$
1
  • $\begingroup$ This really served to clarify my confusion, thank you so much $\endgroup$
    – manis
    May 7 '14 at 9:24
0
$\begingroup$

Hint: Prove by induction that $$ T(n) = 2^{n/2} T(0) + 2^{n/2+2} - n - 4. $$ (See the calculation in my answer to your former question.) Alternatively, you can try proving by induction that $T(n) \leq c 2^{n/2} - n$, for an appropriate $c$. Let us know if that works.

More generally, what you call the substitution method is used to get a bound on some recurrence without solving the recurrence explicitly. If you already know the explicit solution, and the explicit solution yields itself to asymptotic analysis, then there is no reason to use the substitution method other than to get a possibly shorter proof, or one that is more easy to generalize.

I realize that there is one more reason, namely that the exercise requires you to use the substitution method, but in that case you can defeat this silly and narrow request by using the substituting method to find the exact asymptotics.

$\endgroup$
5
  • $\begingroup$ Yes, I am trying to prove it using the substituion method, but I am confused why my calculation doesn't uphold the inequality $\endgroup$
    – manis
    May 5 '14 at 13:46
  • 1
    $\begingroup$ @manis Because it doesn't work. The substitution method isn't a complete method – not everything which is true can be proved using the method, and furthermore in your case you need to slightly modify the induction hypothesis by subtracting $n$. Ask your professor why they didn't teach you this variant of the method. $\endgroup$ May 5 '14 at 13:48
  • $\begingroup$ Can you try to explain why i am allowed to just change the hypothesis like that? If I subtract n, then I'm not testing if T(n)=O(2^(n/2)) anymore, but rather T(n)=O(2^(n/2)-n), even though the former is correct? $\endgroup$
    – manis
    May 5 '14 at 13:55
  • $\begingroup$ @manis It's mathematics, you can do whatever you want as long as it's according to the "rules". We obviously have a different conception of the rules. As you demonstrate, the induction hypothesis $T(n) \leq c2^{n/2}$ isn't strong enough ("doesn't work"). So you need to do something else. That's life. $\endgroup$ May 5 '14 at 13:59
  • 1
    $\begingroup$ @manis Note that $O(2^{\frac n2}) = O(2^{\frac ns}-n)$. (Remember that $O(\cdot) are just classes of funtions.) $\endgroup$
    – FrankW
    May 5 '14 at 14:09

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