Решение рекуррентного отношения с использованием итерационного метода

Question

как решить T(n) = T(n-1) + n, используя итерационный метод и ответ theta(n^2)

Answer 1

T(n) = T(n-1) + n = T(n-2) + n-1 + n = ... = 1+ 2 + ... + n = (n+1)n/2 = theta(n^2)

обратите внимание на предположение, что T (0) = 0 (у вас должна быть база для рекурсии)
надеюсь, что вы имели в виду

Answer 2

Иногда вы также можете использовать метод уравнений характеристик для решения рекуррентных отношений. Это включает определение Частного интеграла и полного решения.

Больше информации здесь: решение рекуррентных отношений