World's most popular travel blog for travel bloggers.

, ,
Problem Detail:

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.

#### Answered By : Rick Decker

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.