确定重复关系的运行时间T（n）= T（n-1）+ n

Question

如何确定输入大小为n的算法的满足递归关系的算法的运行时间（以Big-Theta表示）T(n) = T(n-1)+n其中n >= 1和初始条件T(1) = 1？

编辑：我练了过去的答卷。被困在这个问题上。需要指导

Answer 1

看看这样说：T(n) = T(n-1) + n = T(n-2) + (n-1) + n = T(n-3) + (n-2) + (n-1) + n。这意味着如果n> = 1，那么你将得到类似T（N）= 1 + 2 + 3 + ... + N。如果你的工作本系列的模式，你会看到(n+1)n/2。因此，Ө(n^2)