←back to thread

A visual introduction to big O notation

(samwho.dev)
688 points samwho | 3 comments | 24 Aug 25 07:39 UTC | HN request time: 0s | source
Show context
IceDane ◴[25 Aug 25 17:59 UTC] No.45016742[source]▶
Every time I see an introduction to Big-O notation, I immediately go look for a section about the worst case to find the most common, fundamental misconception that is present in nearly every such text.

Lo and behold:

> Because it's common for an algorithm's performance to depend not just on the size of the input, but also its arrangement, big O notation always describes the worst-case scenario.

This is not true. I'm on my phone, so I can't be bothered to explain this in more detail, but there is plenty of information about this online.

replies(4): >>45016873 #>>45016884 #>>45016889 #>>45017375 #
bonoboTP ◴[25 Aug 25 18:08 UTC] No.45016884[source]▶
Yes. The notation can be used to describe how fast any function grows. That function may be a worst-case runtime wrt. input length, the average-case runtimve wrt. input length, or anything else, really.

But the most common usage is indeed worst-case analysis, especially in intro courses.

This is also wrong in the article:

> You may sometimes see the Greek letter "theta", Θ, instead of the letter O in big O notation. This is used when the best and worst case have the same order of growth. We can't use it for bubble sort because the best case is O(n) and the worst case is O(n^2).

It conflates two different, orthogonal concepts: upper vs lower bounds on the one hand, and best vs worst case analysis on the other.

The phrase "the best case is O(n)" already contradicts "big O notation always describes the worst-case scenario". They clearly use it for best case right there in the article.

replies(2): >>45016968 #>>45016973 #
1. ayhanfuat ◴[25 Aug 25 18:14 UTC] No.45016973[source]▶
> 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.

replies(2): >>45020678 #>>45026494 #
2. tialaramex ◴[26 Aug 25 00:02 UTC] No.45020678[source]▶
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.

3. namibj ◴[26 Aug 25 13:46 UTC] No.45026494[source]▶
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