如何通过迭代法求解 T(n)=T(n-1)+ (n-1)？

Question

请任何人都可以帮我解决这个问题：使用迭代方法 T (n) = T (n - 1) + (n - 1) 解决

并证明 T (n) ?? (n²)

拜托，如果你能一步一步地解释，我将不胜感激。

Answer 1

我解决了一个简单的方法：

T (n) = T (n - 1) + (n - 1)-----------(1)
//now submit T(n-1)=t(n)

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

now submit (2) in (1) you will get
i.e T(n)=[T(n-2)+n-2]+(n-1)
T(n)=T(n-2)+2n-3 //simplified--------------(3)

now, T(n-2)=t(n)
 T(n-2)=T((n-2)-2)+[2(n-2)-3]
T(n-2)=T(n-4)+2n-7---------------(4)
now submit (4) in (2) you will get
i.e T(n)=[T(n-4)+2n-7]+(2n-3)
T(n)=T(n-4)+4n-10 //simplified
............
T(n)=T(n-k)+kn-10

now, assume k=n-1

T(n)=T(n-(n-1))+(n-1)n-10
T(n)=T(1)+n^2-n-10
According to the complexity 10 is constant

So , Finally O(n^2)