Recursive Runtime of T(n-k)

Question

I am trying to find the runtime of the equation;

T(n) = T(n-2) + n³.

When I am solving it I arrive at the summation T(n) = T(n-k) + Σ_{k = 0,...,n/2}(n-2k)³.
Solving that sum I get 1/8(n²)(n + 2)². Solving this I would get the runtime to be Θ(n⁴).
However, I think I did something wrong, does anyone have any ideas?

Answer 1

Why do you think that it is wrong? This equation is clearly Theta(n^4)

The more detailed solution can be obtained from WolframALpha (did you know it solves recurrence equations?)

https://www.wolframalpha.com/input/?i=T%28n%29%3DT%28n-2%29%2Bn%5E3

You can also add some border cases, like T(0)=T(1)=1

https://www.wolframalpha.com/input/?i=T%28n%29%3DT%28n-2%29%2Bn%5E3%2C+T%281%29%3D1%2C+T%282%29%3D1

and finally: asymptotic plot, showing that it truly behaves like n^4 function

Answer 2

Here is an attempt to show your recursive recursive recurrence with steps:

With WolframAlpha engine solving the summation.