Take the 2-minute tour ×

I have this recurence 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) <= c*(n-2)² (induction hypothesis)

2(c*(n-2)²) + n <= cn² (substitution)

cn²-8c + n <= cn²

Can anyone see where I go wrong? I also tried for even larger O(n^x) but i still doesnt work.

share|improve this question

closed as off-topic by Oliver Charlesworth, Dukeling, Joce, minitech May 4 '14 at 14:10


This question appears to be off-topic because it is about maths (try cs.stackexchange.com). –  Oliver Charlesworth May 4 '14 at 13:34
this is part of the CS curriculum so i though it would be fine –  manis May 4 '14 at 13:40
It's CS maths, which is why you should ask at the CS stack-exchange. –  Oliver Charlesworth May 4 '14 at 13:40
yeah my bad, sorry –  manis May 4 '14 at 13:42

1 Answer 1

Well, this is because it is NOT O(n^2), In fact, this is Omega(2^(n/2))

p(n) = 2p(n-2) + n = 2(2(p(n-4) + n-2) + n = 
     = 2(2(2(p(n-6) + n-4) + n-2) + n = .... =
     = 2^(n/2) * 1 + 2^(n/2-1) * 3 + ... + 2^1 (n-2) + 2^0 * n

From the above you can see that the recurrence is NOT O(n^2), since the very first element in the sum is 2^(n/2), which is much larger than O(n^2) for sufficiently large values of n.

Since it seems like homework, I'd rather let you try and solve it on your own from here, after the initial mistake is clear.

Good luck!

share|improve this answer
