Give an upper bound for Tn Tn 1 n using the substitution m

Give an upper bound for T(n) = T(n 1) + n, using the substitution method. Next, give a lower bound by flipping the inequality.

Solution

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

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

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

.

.

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

Hence, T(n) belongs to O(n²)