[解決済み] 簡単：T(n)=T(n-1)+nを反復法で解く。

質問

どなたか、この件に関して助けていただけませんか？

反復法を用いて解く。 T(n) = T(n-1) +n

手順の説明をお願いします。

どのように解決するのですか？

T(n) = T(n-1) + n

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

T(n-2) = T(n-3) + n-2

というように、T(n-1)とT(n-2)の値をT(n)に代入すると、大体のパターンを把握することができます。

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

T(n) = T(n-3) + n-2 + n-1 + n
.
.
.

T(n) = T(n-k) + kn - k(k-1)/2    ...(1)

ベースケースの場合。

n - k = 1 so we can get T(1)

=> k = n - 1
に代入する。

  T(n) = T(1) + (n-1)n - (n-1)(n-2)/2

これは、次数 n であることがわかります。 ² => O(n ² ).