1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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)$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.