I'm aware that the worst case scenario recurrence relation corresponding equation is: $$ T(n) = T(n-1) + T(0) + \Theta(n) $$

However, I really don't get how the last term $ \Theta(n)$ was determined.

  1. I dont understand why $ \Theta(n)$ and not $ \mathcal{O}(N) $
  2. I don't get why it is $ \Theta(N) $ and not $ \Theta(N-1) $ because in quick sort you compare the pivot with (n-1) elements, not "n" elements.

Specially the number 2 it's hard for me to understand.

  • 1
    $\begingroup$ $\Theta(N)=\Theta(N-1)$ Look at the definition of big-theta. $\endgroup$ Nov 12, 2023 at 15:56
  • $\begingroup$ @RickDecker Oh! I get it, Θ(N) or Θ(N−1) doesn't matter, the constant difference does not affect the growth rate of the function!! Does it makes sense? However, about the question number 1, why Big Thetha and not Big O? $\endgroup$
    – RodrigoAlb
    Nov 12, 2023 at 16:42
  • $\begingroup$ @RodrigoAlb First of all theta, $\Theta(f(n))$ implies $O(f(n))$. Moreover, if the recurrence relation used $O(n)$ instead of $\Theta(n)$ then you would only have been able to conclude that $T(n) = O(n^2)$. This mean that QuickSort, in the worst-case, is not slower than $n^2$ (up to multiplicative and additive constants) but it doesn't rule out, e.g., a time complexity of $O(n \log n)$. By using $\Theta(n)$ you can conlude that $T(n) = \Theta(n^2)$, i.e., there are instances were quicksort uses $\Omega(n^2)$ time. $\endgroup$
    – Steven
    Nov 12, 2023 at 16:52
  • $\begingroup$ Big-O(n) means n or faster. Theta(n) means n. So the worst case is indeed n^2 and not “up to n^2”. $\endgroup$
    – gnasher729
    Dec 13, 2023 at 19:31

1 Answer 1

  1. For sure you have to do $n-1$ comparisons with the pivot, you can't do less, so it is $\Omega(n-1)=\Omega(n)$. At the same time you do at most $n-1$ comparisons and swaps. Thus it is $O(n-1)=O(n)$. Thus it is $\Theta(n)$.
  2. As stated in 1., summing constants does not affect asymptothic notation, so $\Theta(n)=\Theta(n-1)$.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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