big-o - 漸化式：T（n-1）のビッグOを解く

Question

私はBigOのいくつかの漸化式の問題を解決していますが、これまでのところ、この形式を含む漸化式にしか遭遇していません。

T(n) = a*T(n/b) + f(n)

上記の場合、BigO表記を見つけるのは非常に簡単です。しかし、私は最近、次の方程式でカーブボールを投げられました。

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

Big Oでこれを解決する方法がよくわかりません。実際に、次のように方程式をプラグインしてみました。

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

これが正しいかどうかは完全にはわかりませんが、行き詰まっていて助けが必要です。ありがとう！

Answer 1

T(1) = 0 と仮定

T(n) = T(n-1) + 2
 = (T(n-2) + 2) + 2
 = T(n-2) + 4
 = (T(n-3) + 2) + 4
 = T(n-3) + 6
 = T(n-k) + 2k

k を n-1 に設定すると、

T(n) = 2n - 2

したがって、それは O(n)

Answer 2

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

したがって、T(n) = 2*n O(n) を意味します