Question

Give asymptotic upper and lower bounds for T(n). Assume that T(n) is constant for n <= 2.

Make your bounds as tight as possible, and justify your answers.

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

Answer 1

Solution:

Given,

=>T(n) = T(n-2) + n^2 for n > 2 and T(n) is constant for 2

Explanation:

Solving recurrence relation using substitution method:

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

=>T(n-2) = T(n-2*2) + (n-2)^2...(2)

From (1) and (2)

=>T(n) = T(n-2*2) + n^2 + (n-2)^2

and so on.

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

=>Let say T(1) = 2

=>n - 2k = 1

=>k = (n-1)/2...(4)

From (3) and (4)

=>T(n) = 1 + n^2 + (n-2)^2 + ... + (n-((n-1)/2 - 1)

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

=>T(n) = 1^2 + 3^2 + 5^2 + .. + n^2 where n is odd

Sum of squares of first n odd numbers

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

=>T(n) = n*(n+1)(n-1)/6

=>Hence T(n) = (n^3)

=>Hence upper bound = O(n^3) and lower bound = (n^3)

I have explained each and every part with the help of statements attached to it.