# Average case complexity and Big-O

In this Wikipedia article on Average-case complexity there is the text:

For example, many sorting algorithms which utilize randomness, such as Quicksort, have a worst-case running time of $$O(n^2)$$, but an average-case running time of $$O(n \log(n))$$, where n is the length of the input to be sorted.

My question is about the use of $$O$$ as our function for analyzing the average-case scenario. My understanding of $$O$$ is, essentially, $$\leq$$, which seems like an odd choice to use for average time, which could be much more tightly defined (perhaps like $$\Theta$$?).

Is Wikipedia correct to use $$O$$ here, and if so, why?

Wikipedia use is correct. The notation $$O(\cdot)$$ denotes a set of function, in particular $$O(f(n))$$ contains all functions $$g(n)$$ for which there is a constant $$c$$ and a choice of $$n_0$$ such that $$g(n) \le c f(n)$$ for all $$n \ge n_0$$.
The average running time of an algorithm is some function of its input size $$n$$. Therefore it is perfectly correct to say that a function belongs to a set of functions.
Notice also that if $$g(n) \in \Theta(f(n))$$ then $$g(n) \in O(f(n))$$.
• You can definitely replace the $O(\cdot)$ notation with the $\Theta(\cdot)$ notation in the Wikipedia sentence while keeping it true and also making it more precise. The $O(n \log n)$ part doesn't really bother me but $O(n^2)$ does. The message the sentence is trying to convey is "while the worst case complexity is quadratic, randomization lowers the average complexity to $n\log n$". I would hence expect a lower-bound on the worst-case complexity (either $\Omega(\cdot)$ or $\Theta(\cdot)$, but not $O(\cdot)$) and an upper bound on the average complexity (either $O(\cdot)$ or $\Theta(\cdot)$) Nov 10, 2021 at 21:07