1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I guess my question is, sure it's technically correct, it's part of that set, but average time can be much more tightly defined, so why would we go with O, which is technically correct for an infinite number of answers. Since we (presumably) have more tightly bound functions available to us, wouldn't one of them be a more appropriate choice? (BTW, just to give a flavor to any response you write, it took me several minutes to understand the answer you wrote -- I don't have a very rich background here, so any efforts you take to keep your responses easy to understand are def. appreciated!) $\endgroup$
    – Ben I.
    Nov 10, 2021 at 20:17
  • 1
    $\begingroup$ 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)$) $\endgroup$
    – Steven
    Nov 10, 2021 at 21:07

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.