# $\Theta$ Notation Question

$$T(n) = T(n-k) + O(n)$$

What is the time complexity in $\Theta$ notation? I tried to create recursion tree but I could find the answer.

I found: $h=n/k$

Sum: $c*n$ + $c*(n-k)$ + $c*(n-2k)$ + .... + $O(1)$

Do you have any ideas?

• Try to represent your answer as a summation. Then you will be able to simplify it. – Hoda Feb 6 '14 at 20:17

Be careful, $O(n)$ means the set of functions $f$ such that there is an upper bound of the form $f(n) \le c n$ for large enough $n$ and a positive $c$; $\Theta(n)$ asserts there are two such limits, $c_l n \le f(n) \le c_u n$. So $0 = O(n)$, and for that specific function the solution is $T(n) = 0$ , which definitely isn't $\Theta(n)$.