Рекурсивный Runtime T (n-k)

Question

Я пытаюсь найти время выполнения уравнения;

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

Когда я ее решения я достигаю суммирования Т (п) = Т (п-к) + S _{к = 0, ..., п/2} (п-2k) ³.
Решая эту сумму, я получаю 1/8 (n²) (n + 2) ². Решив это, я получаю, чтобы время выполнения было Θ (n⁴).
Однако, я думаю, что я сделал что-то не так, есть ли у кого-нибудь идеи?

Answer 1

Почему вы думаете, что это неправильно? Это уравнение, очевидно, Тэта (п^4)

Более подробное решение может быть получено из WolframAlpha (вы знаете, что это решает рекуррентные уравнения?)

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

Вы можете также добавить некоторые границы случаи, как T (0) = Т (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

и наконец: асимптотический сюжет, показывая, что он действительно ведет себя как п^4 функции

Answer 2

Вот попытка показать свое рекурсивное рекурсивное повторение с шагом:

С WolframAlpha engine решая суммирование.