Algorithm complexity means worst case complexity [closed]

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. Closed 10 years ago.

We have best case, average case and worst case time complexities. So someone asks us about the complexity of an algorithm what is 开发者_JAVA百科he referring to?

---

Colloquially: Usually, average case. This is why people say that Quicksort is O(N log N) time and a hash table lookup is O(K) time (K = key size). They are worst case O(N^2) and O(K*N), respectively. I recommend being explicit.

Academically: Usually, worst case. However, in academia people are usually interested in proving the complexity class for a given problem, rather than examining the complexity of an algorithm. For academicians, an algorithm might just be a handy proof for an upper bound on complexity rather than the actual object of study.

The other gotcha is that "average case" is entirely dependent on the input distribution. Most people assume uniform distributions, unless they use the phrase "real world" at which point it's anybody's guess what their input is.