1
$\begingroup$

Big-O describes an upper bound on run time. Is that not the definition of "worst-case"?

For example, how can we say that a hash table insertion require O(1) time on average? Constant time is the best case, n time is the worst case. How can an upper bound describe an average run time? In what sense is that bound "upper"?

Improve this question
$\endgroup$
2
  • $\begingroup$ Please ask one question per post. $\endgroup$
    – fade2black
    Sep 1, 2017 at 2:03
  • $\begingroup$ It's multiple ways of asking the same question for clarity. If you can't follow the plot then you can't follow the plot. $\endgroup$
    – Cow Pow Pow
    Sep 1, 2017 at 2:07

1 Answer 1

Reset to default
2
$\begingroup$

Wikipedia says:

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

So it is not the definition of the "worst case".

Wikipedia defines best, worst, and average cases as

In computer science, best, worst, and average cases of a given algorithm express what the resource usage is at least, at most and on average, respectively.

By resource we usually refer to time or/and space (memory) required to solve a certain problem.

It also says:

Big O notation is a convenient way to express the worst-case scenario for a given algorithm, although it can also be used to express the average-case - for example, the worst-case scenario for quicksort is $O(n^2)$, but the average-case run-time is $O(n\log{n})$.

To sum up: Big-O notation is a pure mathematical concept and notation, which is used in Computer science to express the worst-case scenario for a given algorithm.

Here we have some useful posts:

Improve this answer
$\endgroup$
3
  • $\begingroup$ > [Definition of Big O] is not the definition of the "worst case". > Big-O notation ... is used in Computer science to express the worst-case scenario for a given algorithm. $\endgroup$
    – Cow Pow Pow
    Sep 1, 2017 at 18:46
  • $\begingroup$ @CowPowPow You should differentiate "to express" and "definition of". For example, we express the velocity $v(t)$ as the integral $\int a(t)dt$ of the acceleration, but it does not make the integral to be the definition of the velocity, does it? Integral exists independently from the velocity as Big-O exists independently from the worst/average case analysis. $\endgroup$
    – fade2black
    Sep 1, 2017 at 18:54
  • $\begingroup$ Yeah actually that is a definition. That's exactly what the word "definition" means in english. $\endgroup$
    – Cow Pow Pow
    Sep 2, 2017 at 20:21

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