←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 #
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 #
ndriscoll ◴[25 Aug 25 18:20 UTC] No.45017060[source]▶
In order to write f(n) is O(g(n)), you already had to smuggle in the idea that you were talking worst case before even talking about O(*). What is f? Typically it is the max of "steps taken" over all input problems of size n. i.e. the worst case.

The O(g(n)) part says f is asymptotically bounded by g(n) up to some constant factor.

replies(1): >>45017124 #
1. samwho ◴[25 Aug 25 18:23 UTC] No.45017124[source]▶
This is how you would explain it?
replies(1): >>45017313 #
2. ndriscoll ◴[25 Aug 25 18:37 UTC] No.45017313[source]▶
If you're just trying to explain what f~O(g) means, then it makes sense to talk in terms of functions and asymptotes like you would in an intro to calculus, sure. Then, separately, computer scientists are interested in f(n) = max_{|S|=n} steps_required(program, S) where S is some input/problem type with some notion of size.

The fact that f looks innocuous but is secretly actually this complicated thing is perhaps the stumbling block for people. The actual O(*) part is just "line stays at or below other line once you go far enough out" (with a slight tweak to allow you to pre-stretch the bounding line).

replies(1): >>45017400 #
3. samwho ◴[25 Aug 25 18:43 UTC] No.45017400[source]▶
I'm aiming this at junior software engineers without math or computer science backgrounds. My own computer science background is very old at this point, and I never did have the math. So I'm not surprised I've made mistakes that are being pointed out by folks that live and breathe this stuff. I want to impart enough useful (if not strictly correct) information to folks to make a difference in their day jobs.