Show that Tn Tn 1 n is n 2 using the substitution method

Show that T(n) = T(n 1) + n is (n ² ) using the substitution method. Hint: Show that cn² T(n) for some c and n n₀. You may find it easier to show that T(n) cn²

Solution

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

Adding all the above equation will give:

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

Let us assume T(0) = 0.

So T(n) = (n*(n+1))/2

Let us take c = 1/4 and n0 = 1

for n 1

(n^2)/2 > (n^2)/4

So (n^2+n)/2>(n^2)/2 > (n^2)/4

We know T(n) = (n^2 + n)/2

So T(n) > c(n^2)

So T(n) is (n^2)