0
$\begingroup$

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

Thanks in advance.

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

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

$\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.