3 ms·
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
by schabernakk 14y ago
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.)
- 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.