Algorithm Complexity Means Worst Complexity

We have the best cases, the average case and the worst time difficulties. So, someone asks us about the complexity of the algorithm, what does it refer to?

+4
source share
1 answer

Conversation: Usually an average case. That's why people say that Quicksort is O (N log N) time, and hash table search is O (K) time (K = key size). This is the worst case of O (N ^ 2) and O (K * N) respectively. I recommend being explicit.

Academic: Usually the worst case. However, in academia, people are usually interested in proving the complexity class for a given problem, rather than studying the complexity of the algorithm. For academics, the algorithm may just be a convenient proof for the upper bound of complexity, and not for the actual object of study.

Another way is that the โ€œaverage caseโ€ is completely dependent on the input distribution. Most people accept uniform distributions, unless they use the phrase "real world," at which point no one realizes what their contribution is.

+6
source

All Articles