Question

Use the substitution method to show that T(n) = T(n − 1) + n has a closed-form solution of O(n^2 ).

Answer 1

Using substitution method
T(n) = T(n-1) + n

T(n)
= T(n-1) + n
= T(n-2) + n-1 + n
= T(n-3) + n-2 + n-1 + n
= T(1) + 2 + ... + n-2 + n-1 + n
= 1 + 2 + ... + n-2 + n-1 + n
This is sum of first n natural numbers. It's formula ius n(n+1)/2.
= n(n+1)/2
= n^2+n/2
we can ignore lower order terms and constant factors.
so, time complexity is O(n^2)
T(n) = O(n^2)