←back to thread

A visual introduction to big O notation

(samwho.dev)
688 points samwho | 4 comments | 24 Aug 25 07:39 UTC | HN request time: 0.001s | 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 #
tromp ◴[25 Aug 25 18:41 UTC] No.45017375[source]▶
O() doesn't necessarily describe worst-case behaviour. It just provides an asymptotic upper bound. So a quadratic sorting algorithm can still be said to be O(n^3), although that might be a little misleading.
replies(2): >>45017466 #>>45022188 #
didibus ◴[26 Aug 25 04:11 UTC] No.45022188[source]▶
In math that’s true, but a practitioner software engineer uses it to mean the common "tightest" upper bound we can easily prove for the case we care about (worst, amortized, average, etc.), and not the actual tightest possible bound.
replies(2): >>45022710 #>>45038283 #
monkeyelite ◴[26 Aug 25 05:46 UTC] No.45022710[source]▶
It has a meaning already - and that is the sets of function which satisfy the condition. So O(n^2) is a subset of O(n^3)
replies(3): >>45025082 #>>45029524 #>>45029629 #
1. didibus ◴[26 Aug 25 17:18 UTC] No.45029524[source]▶
> It has a meaning already

Natural language tends to work like that, many words take on different meaning in different context, and the dictionary often needs to add alternate definitions as language evolves.

If you come to a software engineering interview and take the mathematical meaning and answer O(n^3), you won't get the job. You need to know the linga franca of the trade, not just the textbooks.

I know this can be frustrating, I just wouldn't really recommend staking your ground on this mountain.

The other mistake, is to assume the interviewer doesn't know better, and you do, and try to explain their mistake. A lot of them know very well, you simply didn't understand correctly the ask because you got confused with the context of the problem statement, and it shows you didn't adapt to the working environment successfully.

And if you think that's bad, wait till you talk to product ;)

replies(1): >>45031477 #
2. monkeyelite ◴[26 Aug 25 19:51 UTC] No.45031477[source]▶
You’re describing a situation of poor communication - not a fault for using the precise definition of Big oh.
replies(1): >>45042720 #
3. didibus ◴[27 Aug 25 17:49 UTC] No.45042720[source]▶
You know the correct definition of BigO, which is great. Where things fell short was recognizing how industry jargon often stretches textbook terms. The skill is being able to adapt, realize when people are talking about a related but different concept, and engage on that level. The strongest candidates handle both the theory and the communication.

So I'd ding the candidate for poor communication.

replies(1): >>45047577 #
4. monkeyelite ◴[28 Aug 25 02:12 UTC] No.45047577{3}[source]▶
You're not engaging with the content of my comment and larping as my hiring manager - dinged for poor communication.