4 ms·
> But the most common usage is indeed worst-case analysis, especially in intro courses. It is also the most sensible one. Best case version is basically useles
by ayhanfuat 1y ago
> But the most common usage is indeed worst-case analysis, especially in intro courses.
It is also the most sensible one. Best case version is basically useless, if you are lucky you may end up with O(1) but that doesn't tell you anything. Average case could be good but it requires you to estimate the distribution.
- tialaramex 1y agoYou'd think, but one of the world's most popular C++ stdlib implementations (Clang's libcpp) shipped the actual Quicksort, which has O(N squared) worst case as its default sort until just a few years ago. Because the typical case for Quicksort is fast, so, most C++ programmers didn't notice. And I really do mean just a few years. Like, Joe Biden was President.
- namibj 1y agoOr, instead of "estimate the distribution" look at what conceptual properties of the instance the big-O cares about. And then derive big-O in terms of such properties. See for example Tetris-LoadBalanced and Tetris-Reordered (on top of Tetris-LoadBalanced) for such works: https://arxiv.org/abs/1909.12102 https://arxiv.org/abs/1909.12102