I have this recurrence $p(n) = 2p(n-2) + n$, and I have guessed that the solution is $O(n^2)$, however, when I do the following calculations, I cannot get the inequality to hold

$p(n-2) \leq c(n-2)^2$ (induction hypothesis)

$2c(n-2)^2 + n \leq cn^2$ (substitution)

$cn^2-8c + n \leq cn^2$

Can anyone see where I go wrong? I also tried for even larger $O(n^x)$ but it still doesn't work.

  • $\begingroup$ Still cant get it to work, could you perhaps show some of the steps? $\endgroup$
    – sfsd
    May 4 '14 at 15:15
  • $\begingroup$ @Guildenstern You should make that an answer. $\endgroup$
    – Raphael
    May 4 '14 at 19:23
  • 1
    $\begingroup$ Our reference question seems to have everything needed to solve this recurrence: cs.stackexchange.com/q/2789/755 $\endgroup$
    – D.W.
    May 5 '14 at 3:44

Using the so-called substitution method, we get (for even $n$) $$ \begin{align*} p(n) &= 2p(n-2) + n \\ &= 4p(n-4) + 2(n-2) + n \\ &= 8p(n-6) + 4(n-4) + 2(n-2) +n \\ &= \cdots \\ &= 2^{n/2} p(0) + 2^{n/2-1} 2 + 2^{n/2-2} 4 + \cdots + 2^0 n. \end{align*} $$ Let's assume for simplicity that $p(0) = 0$. We can write $$ p(n) = \sum_{k=0}^{n/2-1} 2^k (n-2k) = 2^{n/2+2} - n - 4 = \Theta(2^{n/2}). $$ (Solution courtesy of Wolfram alpha.)


It isn't $O(n^2)$.

Hint: $p(1)=1,p(2)=2, p(n)=p(n−2)+n$ is $O(n^2)$, but notice in what way your recurrence relation is different from this one. Try expanding it (yours). And it isn't $O(n^c)$ for some constant $c$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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