←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: 0.496s | 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 #
samwho ◴[25 Aug 25 18:08 UTC] No.45016889[source]▶
It’s okay, you’re not the first to point it out to me!

I’d be interested to hear how you would explain it when you’re at a more appropriate device.

replies(4): >>45017003 #>>45017060 #>>45017631 #>>45018258 #
1. mminer237 ◴[25 Aug 25 19:56 UTC] No.45018258[source]▶
I would just say "almost always" to cut off the pedants. You do use the same notation to describe the best-case and average-case as well; people just don't care about those as often.
replies(2): >>45018497 #>>45019948 #
2. samwho ◴[25 Aug 25 20:19 UTC] No.45018497[source]▶
I did push up a rewording that hopefully lands better. Fingers crossed.
3. jibal ◴[25 Aug 25 22:31 UTC] No.45019948[source]▶
Pejoratively referring to people as "pedants" simply because they know what they are talking about is quite the ad hominem fallacy.

As for what people care about, it depends on what they're doing and what they know about the input distribution. If you're concerned about DOS attacks or response time in a game, then worse case is of primary importance. But if you're paying for wall time then you measure a hash table lookup by its O(1) average time, not its O(n) worst case time.