←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.669s | 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 #
1. samwho ◴[25 Aug 25 18:47 UTC] No.45017466[source]▶
I'd love to hear more about how a quadratic sorting algorithm could be said to be O(n^3). That isn't intuitive to me.
replies(2): >>45017698 #>>45017700 #
2. ndriscoll ◴[25 Aug 25 19:08 UTC] No.45017698[source]▶
Because |n^2|≤|n^3| as n→∞, so if |f| ≤ A|n^2| as n→∞, then |f| ≤ A|n^3| as n→∞.
3. mfsch ◴[25 Aug 25 19:08 UTC] No.45017700[source]▶
Technically the big O notation denotes an upper bound, i.e. it doesn’t mean “grows as fast as” but “grows at most as fast as”. This means that any algorithm that’s O(n²) is also O(n³) and O(n⁴) etc., but we usually try to give the smallest power since that’s the most useful information. The letter used for “grows as fast as” is big Theta: https://en.wikipedia.org/wiki/Big_O_notation#Use_in_computer...
replies(1): >>45017800 #
4. samwho ◴[25 Aug 25 19:17 UTC] No.45017800[source]▶
Ahh I see, thank you!