3 ms·
Isn't that why we look at best/average _and_ worst case? Not only the worst case alone?
by patrickg 14y ago
Isn't that why we look at best/average _and_ worst case? Not only the worst case alone?
- schabernakk 14y agoMy 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.)
- tensor 14y agoIt 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.