Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

> 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.



Or, 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


You'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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: