Hacker News Reader

Isn't that why we look at best/average _and_ worst case? Not only the worst case alone?

My thought exactly. Quicksort for example has an average case of n log n, just like mergesort.

Also, Big-O notation can primarily be used to see how algorithms scale with larger datasets. Not to see which algorithm is faster. (Although in a lot of cases, the better O-notation algorithm is also the faster one.)

It seems that analytic combinatorics (what is advocated instead of big-Oh) is the modern study of things like average case analysis. That said, it seems like bad advice to advocate ignorance of the worst case. Both average and worst cases should be considered.

Reply on news.ycombinator.com