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.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ The same recurrence relation is/has been discussed here, so maybe you can glean something from that. $\endgroup$
    – Guildenstern
    May 5, 2014 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, 2014 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$
    – Guildenstern
    May 5, 2014 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, 2014 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$
    – Yuval Filmus
    May 5, 2014 at 14:30

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This really served to clarify my confusion, thank you so much $\endgroup$
    – manis
    May 7, 2014 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.

Improve this answer
$\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, 2014 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$
    – Yuval Filmus
    May 5, 2014 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, 2014 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$
    – Yuval Filmus
    May 5, 2014 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, 2014 at 14:09

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