Finding a tight bound for a recurrence relation 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?
You just need to expant it (suppose $n$ is even) and using mathematical induction:
$$T(n) = n + (n-2) + T(n-4) = n + (n-2) + (n-4) + \cdots + 4 + 2 = $$
$$2 ( 1 + 2 + \cdots + \frac{n}{2}) = 2\frac{\frac{n}{2}(\frac{n}{2}+1)}{2} = \frac{n(n+2)}{4} = \Theta(n^2)$$