4 ms·
When I did tutoring for an algorithms class, we’d generally make gestures at the fact that the big-O cost doesn’t tell you everything. But I can’t think of any
by bee_rider 3y ago
When I did tutoring for an algorithms class, we’d generally make gestures at the fact that the big-O cost doesn’t tell you everything. But I can’t think of any way to handle that on a systemic level. Just plot n vs t and observe they the big-O prediction comes true for large n, but it gets complicated for small.
After all, nobody would have invented big-O if it wasn’t much easier than the alternative!
- hinkley 3y agoACM papers on sorting algorithms tend to plot run time versus n to show that their novel optimization to sorting pulled ahead of more general algorithms at certain ranges of n. In the early 00's I saw a handful of papers from different teams who came up with algorithms that had much flatter time curves than mergesort for n > 10000.
- bee_rider 3y agoMergesort is the most beautiful sorting algorithm though.