Problem:

Give tight asymptotic bounds $( Theta )$ for the following function:

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

Answer:

We are not given the base case. I am going to assume that $T(0) = 0$ and $T(1) = 1$. Here are some

values for the function.

$$T(2) = T(0) + 2 = 2$$

$$T(3) = T(1) + 3 = 4 $$

$$T(4) = T(2) + 4 = 6 $$

$$T(5) = T(3) + 5 = 9 $$

$$T(6) = T(4) + 6 = 12 $$

$$T(7) = T(5) + 7 = 16 $$

$$T(8) = T(6) + 8 = 20 $$

$$T(9) = T(7) + 9 = 25 $$

$$T(10) = T(8) + 10 = 30 $$

It is growing faster than $O(n)$ time. I am fairly sure that $T(n) in O(n^2)$. That is, $O(n^2)$ is an

upper bound. If $T(n)$ is $theta(n^2)$ then going from $n = 5$ to $n = 10$ we would expect, about, a

factor of $4$ increase. We got an increased by a factor of $frac{ 10}{3}$. I am thinking that the correct answer is:

$$T(n) = Theta(n^2)$$.

However, I do not know how to prove that it is correct? or disprove it?