# Worst Case Scenario Quick Sort

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.

• $\Theta(N)=\Theta(N-1)$ Look at the definition of big-theta. Nov 12, 2023 at 15:56
• @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? Nov 12, 2023 at 16:42
• @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. Nov 12, 2023 at 16:52
• 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”. Dec 13, 2023 at 19:31

## 1 Answer

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