Question

Give the asymptotic bounds for T(n) in each of the following recurrences. Make your bounds as tight as possible and justify your answers. Assume the base cases T(0)=1 and/or T(1) = 1.

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

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

Answer 1

1.

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

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

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

..............

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

For k = n, we get

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

Hence, T(n) = O(n²) [Since 2n + 2(n-1) + 2(n-2) + .... + 2 is twice the sum of first n natural numbers which is of order n²]

2.

T(n) = T(n-2) = 3

= T(n-4) + 3 + 3

= T(n-6) + 3 + 3 + 3

-------------

= T(n - 2*k) + 3*k

For k = n/2, we get

T(n) = T(0) + 3 * n/2

= O(n)