Решение рекуррентного отношения: T (n) = T (n-1) + n-1

Question

Меня попросили решить эту рецидивирующую связь. Я получил следующее решение: https://imgur.com/a/xWoTI40

Поэтому я решил спросить своего учителя, правильно ли это. Он сказал мне, что это не так; и что это правильное решение: https://imgur.com/a/CGD0ta8

Я сейчас совершенно не в курсе. Самое большее, что я пытаюсь понять, почему мое неправильно; самое большее, я думаю, что это действительно правильно.

Может кто-нибудь объяснить?

Answer 1

Ваше решение верное.Вот другой подход с тем же результатом:

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

Решение учителя неверно после второго знака =.Вот что написал учитель:

t(n-1) + n - 1 = t(n-2) + n - 1 - 2

Но на самом деле следующее верно:

t(n-1) + n - 1 = ( t(n-2) + n - 2 ) + n - 1

, что на самом деле именно то, что вы получили.Похоже, что учитель отбросил термин n.

Фактически, решение учителя заканчивается доминирующим термином -n^2, что явно неверно, как t(n) >= 0 для всех n >= 0.