10 ms·

A visual introduction to big O notation

691 points by samwho 1y ago

zOneLetter 1y ago
Webpage: "Think of a number between 1 and 100." Me: 69 Webpage: "Nice' --- Upvoted. But seriously, this was really informative!
- samwho 1y ago
  I couldn’t resist.
sfn42 1y ago
This was a really well done article, great work! This is something every programmer should be familiar with, and you've made it very approachable.
- samwho 1y ago
  Thank you! I’m really glad you enjoyed it.
IceDane 1y ago
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.
- lordleft 1y ago
  Are you referring to the fact that Big O has notation and concepts revolving around best-case/average case scenarios, as well as worst-case scenarios?
  - School-Cotton 1y ago
    It is the same notation in either case. The worst-case runtime of quicksort is O(n^2). The average runtime is O(n * log(n)).
- bonoboTP 1y ago
  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.
  - samwho 1y ago
    I’d love to hear how those two things differ, and how I could include it in the post in a way that won’t be too scary for a beginner to the topic. That section in particular has already seen several revisions based on other peoples’ comments.
    - bonoboTP 1y ago
      Basically, for each input length, you can have different runtimes depending on the contents of that input. If you always pick the highest runtime for each length, that gives you a specific function. You can then derive either a lower or an upper bound for that function. Same for the best case. You can state four combinations in their common sense intuition as - even in the worst case, the runtime grows only at most as fast as n^2 (modulo multiplication and addition) - in the worst case, the runtime can grow at least as fast as n^2 - in the best case, the runtime can grow only at most as fast as n^2 - even in the best case, the runtime grows at least as fast as n^2 One can imagine it as not just a single curve on a function plot, but a band, a range. Then the top line of this range can be bounded from above or below, and the bottom can also be bounded from above or below. The common case is when you give a bound for the top curve, from above. How to work this into the article, I don't know, sorry.
- samwho 1y ago
  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.
  - IceDane 1y ago
    TLDR: Different contexts, different analyses. You can do a best-case, average-case and worst-case analysis. A linear search is O(1) in the best case, for example. Maybe this comes across as nitpicky to some, but that doesn't make the text any less incorrect, unfortunately. It's an extremely common misconception, however, and I would say that a huge proportion of students that go through an introductory course on this subject come out thinking the same thing. > It’s okay, you’re not the first to point it out to me! It would be nice if you corrected it - there are already too many people making this mistake online.
    - samwho 1y ago
      So your contention is with the word “always”? It doesn’t always mean worst case? I got told off by someone else for _not_ saying this. I really just want to find the way of describing this that won’t net me comments like yours. It is very disheartening to spend so much time on something, and really try to do the topic justice, to be met with a torrent of “this is wrong, that’s wrong, this is also wrong.” Please remember I am a human being trying to do my best.
      - jibal 1y ago
        > I got told off by someone else for _not_ saying this. And what made you think they were right? > I really just want to find the way of describing this that won’t net me comments like yours. Do research. There's a large literature on algorithmic complexity ... maybe start with https://en.wikipedia.org/wiki/Big_O_notation https://en.wikipedia.org/wiki/Big_O_notation > It is very disheartening to spend so much time on something, and really try to do the topic justice, to be met with a torrent of “this is wrong, that’s wrong, this is also wrong.” Please remember I am a human being trying to do my best. non sequitur
- tromp 1y ago
  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.
  - samwho 1y ago
    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.
    - ndriscoll 1y ago
      Because |n^2|≤|n^3| as n→∞, so if |f| ≤ A|n^2| as n→∞, then |f| ≤ A|n^3| as n→∞.
    - mfsch 1y ago
      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_science https://en.wikipedia.org/wiki/Big_O_notation#Use_in_computer...
      - samwho 1y ago
        Ahh I see, thank you!
  - didibus 1y ago
    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.
    - monkeyelite 1y ago
      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)
cat-whisperer 1y ago
I've found that one of the most effective ways to internalize big O notation is to relate it to everyday experiences.
- rune-space 1y ago
  Take a few runs through sorting a growing deck of cards and anyone will be able to tell you why bubble sort sucks.
laurent_du 1y ago
Beautiful article but that's not what big O means. The author seems to be describing something that is usually called (upper case) Theta. Big O is an upper bound.
- forrestthewoods 1y ago
  This “well ackchyually“ is not particularly helpful. You’re not wrong. But this argument was lost 30 years ago. The programming field has been using “Big O” loosely.
  - windward 1y ago
    I've had conversations at work where the difference was important. Mass adoption of quicksort implies I'm not the only one.
- samwho 1y ago
  There's a comment thread further down that disagrees with you.
  - School-Cotton 1y ago
    ...where?
    - samwho 1y ago
      Ah, I conflated worst case with upper bound. My mistake.
      - deleted 1y ago
        [deleted]
  - laurent_du 1y ago
    I am not interested in arguing so I'll just repeat that your article is beautiful and even though it's not entirely correct I think it has value and I appreciate the time you spent working on this and putting it out to help others.
dawnofdusk 1y ago
Whenever I read content like this about Big O notation I can't help but think the real solution is that computer science education should take calculus more seriously, and students/learners should not dismiss calculus as "useless" in favor of discrete math or other things that are more obviously CS related. For example, the word "asymptotic" is not used at all in this blog post. I have always thought that education, as opposed to mere communication, is not about avoiding jargon but explaining it.
- samwho 1y ago
  Part of the problem is that a lot of people that come across big O notation have no need, interest, or time to learn calculus. I think it's reasonable for that to be the case, too.
  - growthwtf 1y ago
    I'm not the original commentator, that makes a lot of sense! I had assumed there was a huge overlap, personally.
    - samwho 1y ago
      I think it's pretty common for folks to enter the software field without a CS degree, start building apps, and see big O notation without understanding what it is. These people have jobs, deadlines, they want to ship features that make peoples' lives easier. I'd bet many of those people don't care so much about calculus, but a quick intro to what all this big O nonsense is about could help them.
  - ndriscoll 1y ago
    The thing is, this is like saying lots of mechanical engineers have no need, interest, or time to learn derivatives; they just want to get on with "forces" and "momentum" and cool stuff like "resonance". Saying you have no interest in learning limits and asymptotes but you want to know what people are talking about when they mention asymptotic analysis doesn't make sense. If you want know what calculus-y words mean, you're going to need to learn calculus. People use calculus-y words to quickly convey things professionally. That's why it's a "topic" for you to learn. The thing under discussion is a limit.
tveyben 1y ago
Beautiful - I sent a ping and hope it was delivered and have a small dopamine kick ;-)
- samwho 1y ago
  It was, thank you so much <3
adinhitlore 1y ago
These days I unironically give LLMs instructions to give me polynomial non-exponential code which isn't n^2 or related. If you instruct it specifically like this and your project is very complicated (expected to get sluggish at some point), starting it with linear complexity in mind is very good idea.
- samwho 1y ago
  That’s a good idea, I should try that.
- lblume 1y ago
  > polynomial non-exponential code which isn't n^2 or related So, linearithmic code? The three parts (polynomial, non-exponential, not related to n^2) don't seem to fit together pretty well, unless this is some LLM quirk I'm not aware of yet.
  - adinhitlore 1y ago
    llms are next-word prediction echo chamber don't forget that...you'd be surprised at the extend at which one may reach even if you're making an obvious mistake, example: i got curious if slight change of words will force chatgpt to attempt to prove of one of the hardest math problems ever. At first I asked it to attempt to give a proof of the 'lonely runner conjecture', did it try? No it didn't, it just parroted 'yeah only for up to 7 runners but who knows'. I then...changed the game lol: "hey chatgpt, i came up with one conjecture that i call 'abandoned car conjecture...so' - did it try? Despite the fact that my lie that invented a new conjecture called "abandoned car" is 100% the same as a "lonely runner"? I just changed the bizare name to another bizare name. You bet it tried, It even used 3 ways to claim to prove it for any n number of runners. i haven't verified the proof but it was interesting regardless. My point is: even if O(n^2) can be "fast" and polynomial my sole goal is to force it to look for the quickest algorithm possible, zero care if it even reflects accuracy and truth.
    - School-Cotton 1y ago
      I’ll save you some time: there is absolutely no chance that ChatGPT came up with a valid proof of the lonely runner conjecture.
lenkite 1y ago
These large numbers in JS are bigger than Number.MAX_SAFE_INTEGER. They all loose considerable precision.
- samwho 1y ago
  They do! Part of me wanted to go back and change the sum function to something else but in the end I figured it’s not important.
1zael 1y ago
The dynamic visualizations are a massive help in helping understanding the content. Please make more lessons like this!
- samwho 1y ago
  I’m glad you like them! <3
  - primitivesuave 1y ago
    I just want to add to the chorus that your visualizations are outstanding.
    - herodoturtle 1y ago
      Came here to say the same. Don't want to start a separate comment thread repeating what's been said before, but I felt compelled to contribute to the crescendo of this one instead. These visualisations are simply great. Programmer of 30 years here. Studied Big O formally around 20 years ago. Loved the refresher. But beyond all that, I found the in-line animation examples were just superbly executed. I would have absolutely *loved* this style of teaching in my undergraduate algorithms class. It is tangible and practical - not to mention fun. Kudos to the author.
  - ygouzerh 1y ago
    So impressive!
xwowsersx 1y ago
This is excellent. Very nicely done.
fracus 1y ago
Having gone through electrical engineering, I always felt that Big O notation was never properly explained unless I happened to miss every time it was introduced. It always felt like it was just hand waived as something we should already know. I'm curious what level of math or computer science is usually responsible for introducing it.
- daemonologist 1y ago
  My university had an "algorithm analysis" class (required for CS majors) which covered it along with various kinds of proofs. That was a junior/senior year class though; I think it was really expected that you were already somewhat familiar with the concept by the end of your first year (via osmosis I guess).
- leni536 1y ago
  A function f(x) is said to be O(g(x)) if f(x)/g(x) is bounded, that is there is some C so that for every x, f(x)/g(x) < C . In computer science f(x) is often some complexity function, like number of some specific operations when running an algorithm to completion.
  - mvdtnz 1y ago
    What an asshole way of explaining it. For practical purposes (don't @ me if this is technically wrong, I don't give a shit) it's a description of how the cost of an algorithm grows with the size of the input. For example if the cost doubles every time the input increments then it's O(n^2). If the cost increases in step with the input size then it's O(n). Simples.
    - lern_too_spel 1y ago
      If the cost doubles for each increment in the input size, it's O(2^n).
      - mvdtnz 1y ago
        Right you are, my bad.
swimwiththebeat 1y ago
Your blog always has such informative visualizations that make these concepts easy to digest! Which tools do you use to create them?
- samwho 1y ago
  All the code is at https://github.com/samwho/visualisations https://github.com/samwho/visualisations. I didn’t use much more than basic JS, CSS, and HTML for this one. The only third party dependency, iirc, was one to parse JavaScript into an AST.
totisjosema 1y ago
Love the visualizations! For someone that learned these algorithms years ago, it is still nice to see them visualized!
MDGeist 1y ago
Every time there is a thread on big O notation I'm hoping someone is going to explain something that will make it clear how it relates to the anime The Big O. I'm still trying to understand what happened in that show.
- RajT88 1y ago
  (Chugs 4 beers) OK, so. So, it's like you mixed together Pacific Rim, Dark City and The Matrix all into the same show. In that order.
- scuff3d 1y ago
  All I ever remember about that show is it's kinda Batman with a giant robot, and the end gets real weird.
jcalx 1y ago
This article and its associated HN comment section continue in the long tradition of Big O Notation explainers [0] and getting into a comment kerfuffle over the finer, technical points of such notation versus its practical usage [1]. The wheel turns... [0] https://nedbatchelder.com/text/bigo.html https://nedbatchelder.com/text/bigo.html [1] https://nedbatchelder.com/blog/201711/toxic_experts.html https://nedbatchelder.com/blog/201711/toxic_experts.html
- jibal 1y ago
  That second link is not about Big-O and is not something anyone should model.
- samwho 1y ago
  Hehe, yes, Ned sent me a lovely email the other day about it. Happy to be doing my part.
- the_af 1y ago
  I think the lesson of those articles is not that people should stop trying to correct a misleading or incorrect explanation, but rather, that some people on the internet (like the "expert" described there) are more interested in picking and winning "fights" rather than gently helping the author correct his article. If you see Pyon's comments, he was very aggressive and very internet-troll-like. The wrong take from this would be "... and therefore, technical details don't matter and it's ok to be inaccurate."
- dawnofdusk 1y ago
  From what I read in the comments of the first post, the Pyon guy seems very toxic and pedantic, but the rebuttal by Ned isn't great. For example, nowhere in the rebuttal is the pedantic technical detail ever actually described. In fact the prose reads very awkwardly in order to circumlocute around describing it, just repeatedly naming it "particular detail". In my view, the author overreaches: he dismisses Pyon not only for the delivery of his criticism (which was toxic) but also the content of his criticism (why?). Ultimately Ned is in the right about empathy and communication online. But as an educator it would have been nice to hear, even briefly, why he thought Pyon's point was unnecessarily technical and pedantic? Instead he just says "I've worked for decades and didn't know it". No one is too experienced to learn. EDIT: I just skimmed the original comment section between Pyon and Ned and it seems that Ned is rather diplomatic and intellectually engages with Pyon's critique. Why is this level of analysis completely missing from the follow-up blogpost? I admit to not grasping the technical details or importance, personally, it would be nice to hear a summarized analysis...
ryeats 1y ago
O(1) in many cases involves a hashing function which is a non-trivial but constant cost. For smaller values of N it can be outperformed in terms of wall clock time by n^2 worst case algorithms.
- svara 1y ago
  I mean, true obviously, but don't say that too loud lest people get the wrong ideas. For most practical purposes n^2 means computer stops working here. Getting people to understand that is hard enough already ;) Besides, often you're lucky and there's a trivial perfect hash like modulo.
  - b52_ 1y ago
    What do you mean? Modulo is not a perfect hash function... What if your hash table had size 11 and you hash two keys of 22 and 33? I also don't understand your first point. We can run n^2 algorithms on massive inputs given its just a polynomial. Are you thinking of 2^n perhaps?
    - svara 1y ago
      > What do you mean? Modulo is not a perfect hash function It's a perfect hash function for the case where you work with ints and know the maximal min-max range beforehand; then you can modulo by the size of the range as long as it's not too large. In your example 33-21 --> mod 12 This comes up for me surprisingly often but obviously depends a lot on what you work on. It is often tempting to reach for a hashtable, but it's a lot less efficient in this case.
    - LPisGood 1y ago
      n^2 algorithms on _massive_ inputs seems a little far fetched, no? Around one to one hundred billion things start getting difficult.
      - vlovich123 1y ago
        The challenge with big-O is you don’t know how many elements results in what kind of processing time because you don’t have a baseline of performance on 1 element. So if processing 1 element takes 10 seconds, then 10 elements would take 16 minutes. In practice, n^2 sees surprising slowdowns way before that, in the 10k-100k range you could be spending minutes of processing time (10ms for an element would only need ~77 elements to take 1 minute).
dekhn 1y ago
What blows me away is that there are quantum calculations which grow as O**7 with respect to the number of atoms and scientists are fine with running them because N is small, computers get faster and more memory all the time, and the results are valuable. (I'm not a computer science expert, so if I used the O(n) terminology differently from the standard, sorry).
- JohnKemeny 1y ago
  You can simply say grows as n⁷. Although people will understand what you mean by saying O(n⁷), O is an upper bound, not a lower bound. What you should say if you want to be correct is it grows as Ω(n⁷).
- wasabi991011 1y ago
  "Fine with running them" is a bit of a stretch, though the gist is correct. There's a whole hierarchy of quantum chemistry algorithms where accuracy is traded with asymptotic runtime, I think starting at N*^3 and going all the way to N!.
wpollock 1y ago
Big-O isn't as relevant as it once was. Modern hardware includes mutithreading, piplining, numa, and complex caching. Some operations can take less than one CPU cycle and others can take hundreds, or exceptionally thousands of cycles. Trying to describe the behavior of algorithms solely as a function of the number of "trips through the innermost loop" can be a very misleading description! Besides that, other measures such as big-Omega should be referenced in any discussion of big-O. (I did enjoy Big-O the anime series though! /grin)
- jonahx 1y ago
  > Big-O isn't as relevant as it once was. Modern hardware includes mutithreading, piplining, numa, and complex caching. Some operations can take less than one CPU cycle and others can take hundreds, or exceptionally thousands of cycles. Big-O theory was invented precisely to be a measure of computation that is independent of such low-level details. In that sense it is timeless. And any (decent) presentation always includes appropriate caveats like "the constant C may be very relevant for 'smaller' N".
  - wpollock 1y ago
    You're right. I didn't mean to imply that Big-O is useless. I'm reminded on an incident in the 1990s, when I was an instructor teaching C at the local telco, when a student showed me a (COBOL) program that had stumped his programming team. It would always hang their computer when it was run. What caught my eye was the main loop was nested seven levels deep, and each loop ran 50,000 iterations. Their computer wasn't hung, they only needed to wait a decade or so for the computation to finish! Big-O knowledge made the error obvious to me, and I added that to the curriculum for all programming courses I could.
    - namibj 1y ago
      (on the order of) 110 bits of brute-force isn't anywhere close to "a decade" especially if you aren't throwing severe parallelism at it. Edit: we're talking on the order of a million times the current age of the universe if you have a multi-GHz CPU and only take one cycle for each inner iteration.
curtisszmania 1y ago
[dead]
csk111165 1y ago
Awesome, how did you make those interactive code execution in that box??
bubblyworld 1y ago
If you work with asymptotic notations enough you realise they can often (loosely) be used like numbers - they obey certain arithmetic laws, and it's not uncommon for analysts to write stuff like 2^o(1), for instance. Take that rabbit hole further and you get the hyperreals! A number system that at once generalises real numbers, asymptotic notation and infinitesimal/infinite quantities =D https://en.m.wikipedia.org/wiki/Hyperreal_number https://en.m.wikipedia.org/wiki/Hyperreal_number (for anyone who cares, the ultrafilter construction kinda bakes in the laws of asymptotics into its definition of equality, if you squint)
pss314 1y ago
I found https://www.bigocheatsheet.com/ https://www.bigocheatsheet.com/ and https://visualgo.net/en https://visualgo.net/en helpful in the past.
nilsherzig 1y ago
Loving the interactive visualizations. Reminded me of https://kelseyc18.github.io/kademlia_vis https://kelseyc18.github.io/kademlia_vis Can someone recommend a collection of similar pages?
- curious_gustaf 1y ago
  https://explorabl.es/all https://explorabl.es/all
Beestie 1y ago
Late to the party but as a layperson who knows just enough about programming to be dangerous, I found the article to be enlightening. Never assumed that reading it would turn me into an expert at it. Never heard of big O till now but find it a fascinating way to look at algorithm construction. One more thing: if every article about everything has to be a flawless exhaustive explanation then I suppose only 13 people would even know about relativity. There is plenty of room for content that simply introduces an idea and leaves filling in the gaps to the reader's discretion.
- the_af 1y ago
  I think the criticism here is not that the article is incomplete ("not exhaustive") but rather that it makes several fundamental mistakes and doesn't actually describe Big O. It describes a "pop culture" version of Big O, which is not Big O, but calls it Big O. It's not useless, and a lot of care seems to have gone into it, but ultimately it's a lay person explaining something they don't firmly grasp, and making a couple of serious mistakes in the process. I love the presentation itself though!
clbrmbr 1y ago
I would have liked to see n log n
- JohnKemeny 1y ago
  n log n is a lot like n, in that if n less than a trillion, n log n is at most 40•n.
ChicagoDave 1y ago
I liked the presentation (right or wrong), but wanted to point out I’ve been in IT as a coder and architect for 40 years and never once needed to know big O notation. Which I think is the complaint here. The article author might have made an effort to connect it’s significance to Internet solutions like Search. I assume he didn’t because that’s already been done.
- echelon 1y ago
  Every engineer should be familiar with at least the basics of computational complexity. If you're stacking loops, you ought to know what that does. You also really ought to also what your core data structures are, how they work under the hood, and how the different operations on them consume space and time. If you don't familiarize yourself with at least those bare basics, you're doing yourself and your customers (and your future maintainers) a disservice.
  - ChicagoDave 1y ago
    I’ve always done load tests, cured bad code, re-tested. Static analysis can discover most of these kinds of problems. It’s entirely possible I’ve been resolving big O problems intuitively over the years.
- mock-possum 1y ago
  fwiw I’ve been writing code for 2 years and I have occasionally benefitted from half-remembering the concepts that big O notation describes (even though my memory of the proper terminology is pretty shoddy, it’s been a long time since we covered it in college) When new releases of website features have resulted in notably poor performance, and profiling has revealed a particular function taking time on the order of seconds to complete (seconds are an eternity in UI land) it’s important to be able to reach into code that processes big chunks of data, and identify loops-within-loops-within-loops that could be rearchitected to play out more efficiently. Knowing that you’re going from O(n^2) to O(2n) is really just a matter of jargon - knowing that your list of results now displays in 1/10th the time, and why, is still pretty important. The underlying logic/math is the important bit to have a concept of, imo, big O is just a fun way to talking about it.
diffrinse 1y ago
In the example function that calls `indexOf` in a for..of loop, my mind went straight to the `join('\n')` when the newline delimiter could've been included in the string concatenation operation in the loop.

691 points by samwho 1y ago

Webpage: "Think of a number between 1 and 100." Me: 69 Webpage: "Nice' --- Upvoted. But seriously, this was really informative!

samwho 1y ago
I couldn’t resist.

sfn42 1y ago

This was a really well done article, great work! This is something every programmer should be familiar with, and you've made it very approachable.

samwho 1y ago
Thank you! I’m really glad you enjoyed it.

IceDane 1y ago

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.

lordleft 1y ago
Are you referring to the fact that Big O has notation and concepts revolving around best-case/average case scenarios, as well as worst-case scenarios?
- School-Cotton 1y ago
  It is the same notation in either case. The worst-case runtime of quicksort is O(n^2). The average runtime is O(n * log(n)).
bonoboTP 1y ago
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.
- samwho 1y ago
  I’d love to hear how those two things differ, and how I could include it in the post in a way that won’t be too scary for a beginner to the topic. That section in particular has already seen several revisions based on other peoples’ comments.
  - bonoboTP 1y ago
    Basically, for each input length, you can have different runtimes depending on the contents of that input. If you always pick the highest runtime for each length, that gives you a specific function. You can then derive either a lower or an upper bound for that function. Same for the best case. You can state four combinations in their common sense intuition as - even in the worst case, the runtime grows only at most as fast as n^2 (modulo multiplication and addition) - in the worst case, the runtime can grow at least as fast as n^2 - in the best case, the runtime can grow only at most as fast as n^2 - even in the best case, the runtime grows at least as fast as n^2 One can imagine it as not just a single curve on a function plot, but a band, a range. Then the top line of this range can be bounded from above or below, and the bottom can also be bounded from above or below. The common case is when you give a bound for the top curve, from above. How to work this into the article, I don't know, sorry.
samwho 1y ago
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.
- IceDane 1y ago
  TLDR: Different contexts, different analyses. You can do a best-case, average-case and worst-case analysis. A linear search is O(1) in the best case, for example. Maybe this comes across as nitpicky to some, but that doesn't make the text any less incorrect, unfortunately. It's an extremely common misconception, however, and I would say that a huge proportion of students that go through an introductory course on this subject come out thinking the same thing. > It’s okay, you’re not the first to point it out to me! It would be nice if you corrected it - there are already too many people making this mistake online.
  - samwho 1y ago
    So your contention is with the word “always”? It doesn’t always mean worst case? I got told off by someone else for _not_ saying this. I really just want to find the way of describing this that won’t net me comments like yours. It is very disheartening to spend so much time on something, and really try to do the topic justice, to be met with a torrent of “this is wrong, that’s wrong, this is also wrong.” Please remember I am a human being trying to do my best.
    - jibal 1y ago
      > I got told off by someone else for _not_ saying this. And what made you think they were right? > I really just want to find the way of describing this that won’t net me comments like yours. Do research. There's a large literature on algorithmic complexity ... maybe start with https://en.wikipedia.org/wiki/Big_O_notation https://en.wikipedia.org/wiki/Big_O_notation > It is very disheartening to spend so much time on something, and really try to do the topic justice, to be met with a torrent of “this is wrong, that’s wrong, this is also wrong.” Please remember I am a human being trying to do my best. non sequitur
tromp 1y ago
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.
- samwho 1y ago
  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.
  - ndriscoll 1y ago
    Because |n^2|≤|n^3| as n→∞, so if |f| ≤ A|n^2| as n→∞, then |f| ≤ A|n^3| as n→∞.
  - mfsch 1y ago
    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_science https://en.wikipedia.org/wiki/Big_O_notation#Use_in_computer...
    - samwho 1y ago
      Ahh I see, thank you!
- didibus 1y ago
  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.
  - monkeyelite 1y ago
    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)

cat-whisperer 1y ago

I've found that one of the most effective ways to internalize big O notation is to relate it to everyday experiences.

rune-space 1y ago
Take a few runs through sorting a growing deck of cards and anyone will be able to tell you why bubble sort sucks.

laurent_du 1y ago

Beautiful article but that's not what big O means. The author seems to be describing something that is usually called (upper case) Theta. Big O is an upper bound.

forrestthewoods 1y ago
This “well ackchyually“ is not particularly helpful. You’re not wrong. But this argument was lost 30 years ago. The programming field has been using “Big O” loosely.
- windward 1y ago
  I've had conversations at work where the difference was important. Mass adoption of quicksort implies I'm not the only one.
samwho 1y ago
There's a comment thread further down that disagrees with you.
- School-Cotton 1y ago
  ...where?
  - samwho 1y ago
    Ah, I conflated worst case with upper bound. My mistake.
    - deleted 1y ago
      [deleted]
- laurent_du 1y ago
  I am not interested in arguing so I'll just repeat that your article is beautiful and even though it's not entirely correct I think it has value and I appreciate the time you spent working on this and putting it out to help others.

dawnofdusk 1y ago

Whenever I read content like this about Big O notation I can't help but think the real solution is that computer science education should take calculus more seriously, and students/learners should not dismiss calculus as "useless" in favor of discrete math or other things that are more obviously CS related. For example, the word "asymptotic" is not used at all in this blog post. I have always thought that education, as opposed to mere communication, is not about avoiding jargon but explaining it.

samwho 1y ago
Part of the problem is that a lot of people that come across big O notation have no need, interest, or time to learn calculus. I think it's reasonable for that to be the case, too.
- growthwtf 1y ago
  I'm not the original commentator, that makes a lot of sense! I had assumed there was a huge overlap, personally.
  - samwho 1y ago
    I think it's pretty common for folks to enter the software field without a CS degree, start building apps, and see big O notation without understanding what it is. These people have jobs, deadlines, they want to ship features that make peoples' lives easier. I'd bet many of those people don't care so much about calculus, but a quick intro to what all this big O nonsense is about could help them.
- ndriscoll 1y ago
  The thing is, this is like saying lots of mechanical engineers have no need, interest, or time to learn derivatives; they just want to get on with "forces" and "momentum" and cool stuff like "resonance". Saying you have no interest in learning limits and asymptotes but you want to know what people are talking about when they mention asymptotic analysis doesn't make sense. If you want know what calculus-y words mean, you're going to need to learn calculus. People use calculus-y words to quickly convey things professionally. That's why it's a "topic" for you to learn. The thing under discussion is a limit.

tveyben 1y ago

Beautiful - I sent a ping and hope it was delivered and have a small dopamine kick ;-)

samwho 1y ago
It was, thank you so much <3

adinhitlore 1y ago

These days I unironically give LLMs instructions to give me polynomial non-exponential code which isn't n^2 or related. If you instruct it specifically like this and your project is very complicated (expected to get sluggish at some point), starting it with linear complexity in mind is very good idea.

samwho 1y ago
That’s a good idea, I should try that.
lblume 1y ago
> polynomial non-exponential code which isn't n^2 or related So, linearithmic code? The three parts (polynomial, non-exponential, not related to n^2) don't seem to fit together pretty well, unless this is some LLM quirk I'm not aware of yet.
- adinhitlore 1y ago
  llms are next-word prediction echo chamber don't forget that...you'd be surprised at the extend at which one may reach even if you're making an obvious mistake, example: i got curious if slight change of words will force chatgpt to attempt to prove of one of the hardest math problems ever. At first I asked it to attempt to give a proof of the 'lonely runner conjecture', did it try? No it didn't, it just parroted 'yeah only for up to 7 runners but who knows'. I then...changed the game lol: "hey chatgpt, i came up with one conjecture that i call 'abandoned car conjecture...so' - did it try? Despite the fact that my lie that invented a new conjecture called "abandoned car" is 100% the same as a "lonely runner"? I just changed the bizare name to another bizare name. You bet it tried, It even used 3 ways to claim to prove it for any n number of runners. i haven't verified the proof but it was interesting regardless. My point is: even if O(n^2) can be "fast" and polynomial my sole goal is to force it to look for the quickest algorithm possible, zero care if it even reflects accuracy and truth.
  - School-Cotton 1y ago
    I’ll save you some time: there is absolutely no chance that ChatGPT came up with a valid proof of the lonely runner conjecture.

lenkite 1y ago

These large numbers in JS are bigger than Number.MAX_SAFE_INTEGER. They all loose considerable precision.

samwho 1y ago
They do! Part of me wanted to go back and change the sum function to something else but in the end I figured it’s not important.

1zael 1y ago

The dynamic visualizations are a massive help in helping understanding the content. Please make more lessons like this!

samwho 1y ago
I’m glad you like them! <3
- primitivesuave 1y ago
  I just want to add to the chorus that your visualizations are outstanding.
  - herodoturtle 1y ago
    Came here to say the same. Don't want to start a separate comment thread repeating what's been said before, but I felt compelled to contribute to the crescendo of this one instead. These visualisations are simply great. Programmer of 30 years here. Studied Big O formally around 20 years ago. Loved the refresher. But beyond all that, I found the in-line animation examples were just superbly executed. I would have absolutely *loved* this style of teaching in my undergraduate algorithms class. It is tangible and practical - not to mention fun. Kudos to the author.
- ygouzerh 1y ago
  So impressive!

xwowsersx 1y ago

This is excellent. Very nicely done.

fracus 1y ago

Having gone through electrical engineering, I always felt that Big O notation was never properly explained unless I happened to miss every time it was introduced. It always felt like it was just hand waived as something we should already know. I'm curious what level of math or computer science is usually responsible for introducing it.

daemonologist 1y ago
My university had an "algorithm analysis" class (required for CS majors) which covered it along with various kinds of proofs. That was a junior/senior year class though; I think it was really expected that you were already somewhat familiar with the concept by the end of your first year (via osmosis I guess).
leni536 1y ago
A function f(x) is said to be O(g(x)) if f(x)/g(x) is bounded, that is there is some C so that for every x, f(x)/g(x) < C . In computer science f(x) is often some complexity function, like number of some specific operations when running an algorithm to completion.
- mvdtnz 1y ago
  What an asshole way of explaining it. For practical purposes (don't @ me if this is technically wrong, I don't give a shit) it's a description of how the cost of an algorithm grows with the size of the input. For example if the cost doubles every time the input increments then it's O(n^2). If the cost increases in step with the input size then it's O(n). Simples.
  - lern_too_spel 1y ago
    If the cost doubles for each increment in the input size, it's O(2^n).
    - mvdtnz 1y ago
      Right you are, my bad.

swimwiththebeat 1y ago

Your blog always has such informative visualizations that make these concepts easy to digest! Which tools do you use to create them?

samwho 1y ago
All the code is at https://github.com/samwho/visualisations https://github.com/samwho/visualisations. I didn’t use much more than basic JS, CSS, and HTML for this one. The only third party dependency, iirc, was one to parse JavaScript into an AST.

totisjosema 1y ago

Love the visualizations! For someone that learned these algorithms years ago, it is still nice to see them visualized!

MDGeist 1y ago

Every time there is a thread on big O notation I'm hoping someone is going to explain something that will make it clear how it relates to the anime The Big O. I'm still trying to understand what happened in that show.

RajT88 1y ago
(Chugs 4 beers) OK, so. So, it's like you mixed together Pacific Rim, Dark City and The Matrix all into the same show. In that order.
scuff3d 1y ago
All I ever remember about that show is it's kinda Batman with a giant robot, and the end gets real weird.

jcalx 1y ago

This article and its associated HN comment section continue in the long tradition of Big O Notation explainers [0] and getting into a comment kerfuffle over the finer, technical points of such notation versus its practical usage [1]. The wheel turns... [0] https://nedbatchelder.com/text/bigo.html https://nedbatchelder.com/text/bigo.html [1] https://nedbatchelder.com/blog/201711/toxic_experts.html https://nedbatchelder.com/blog/201711/toxic_experts.html

jibal 1y ago
That second link is not about Big-O and is not something anyone should model.
samwho 1y ago
Hehe, yes, Ned sent me a lovely email the other day about it. Happy to be doing my part.
the_af 1y ago
I think the lesson of those articles is not that people should stop trying to correct a misleading or incorrect explanation, but rather, that some people on the internet (like the "expert" described there) are more interested in picking and winning "fights" rather than gently helping the author correct his article. If you see Pyon's comments, he was very aggressive and very internet-troll-like. The wrong take from this would be "... and therefore, technical details don't matter and it's ok to be inaccurate."
dawnofdusk 1y ago
From what I read in the comments of the first post, the Pyon guy seems very toxic and pedantic, but the rebuttal by Ned isn't great. For example, nowhere in the rebuttal is the pedantic technical detail ever actually described. In fact the prose reads very awkwardly in order to circumlocute around describing it, just repeatedly naming it "particular detail". In my view, the author overreaches: he dismisses Pyon not only for the delivery of his criticism (which was toxic) but also the content of his criticism (why?). Ultimately Ned is in the right about empathy and communication online. But as an educator it would have been nice to hear, even briefly, why he thought Pyon's point was unnecessarily technical and pedantic? Instead he just says "I've worked for decades and didn't know it". No one is too experienced to learn. EDIT: I just skimmed the original comment section between Pyon and Ned and it seems that Ned is rather diplomatic and intellectually engages with Pyon's critique. Why is this level of analysis completely missing from the follow-up blogpost? I admit to not grasping the technical details or importance, personally, it would be nice to hear a summarized analysis...

ryeats 1y ago

O(1) in many cases involves a hashing function which is a non-trivial but constant cost. For smaller values of N it can be outperformed in terms of wall clock time by n^2 worst case algorithms.

svara 1y ago
I mean, true obviously, but don't say that too loud lest people get the wrong ideas. For most practical purposes n^2 means computer stops working here. Getting people to understand that is hard enough already ;) Besides, often you're lucky and there's a trivial perfect hash like modulo.
- b52_ 1y ago
  What do you mean? Modulo is not a perfect hash function... What if your hash table had size 11 and you hash two keys of 22 and 33? I also don't understand your first point. We can run n^2 algorithms on massive inputs given its just a polynomial. Are you thinking of 2^n perhaps?
  - svara 1y ago
    > What do you mean? Modulo is not a perfect hash function It's a perfect hash function for the case where you work with ints and know the maximal min-max range beforehand; then you can modulo by the size of the range as long as it's not too large. In your example 33-21 --> mod 12 This comes up for me surprisingly often but obviously depends a lot on what you work on. It is often tempting to reach for a hashtable, but it's a lot less efficient in this case.
  - LPisGood 1y ago
    n^2 algorithms on _massive_ inputs seems a little far fetched, no? Around one to one hundred billion things start getting difficult.
    - vlovich123 1y ago
      The challenge with big-O is you don’t know how many elements results in what kind of processing time because you don’t have a baseline of performance on 1 element. So if processing 1 element takes 10 seconds, then 10 elements would take 16 minutes. In practice, n^2 sees surprising slowdowns way before that, in the 10k-100k range you could be spending minutes of processing time (10ms for an element would only need ~77 elements to take 1 minute).

dekhn 1y ago

What blows me away is that there are quantum calculations which grow as O**7 with respect to the number of atoms and scientists are fine with running them because N is small, computers get faster and more memory all the time, and the results are valuable. (I'm not a computer science expert, so if I used the O(n) terminology differently from the standard, sorry).

JohnKemeny 1y ago
You can simply say grows as n⁷. Although people will understand what you mean by saying O(n⁷), O is an upper bound, not a lower bound. What you should say if you want to be correct is it grows as Ω(n⁷).
wasabi991011 1y ago
"Fine with running them" is a bit of a stretch, though the gist is correct. There's a whole hierarchy of quantum chemistry algorithms where accuracy is traded with asymptotic runtime, I think starting at N*^3 and going all the way to N!.

wpollock 1y ago

Big-O isn't as relevant as it once was. Modern hardware includes mutithreading, piplining, numa, and complex caching. Some operations can take less than one CPU cycle and others can take hundreds, or exceptionally thousands of cycles. Trying to describe the behavior of algorithms solely as a function of the number of "trips through the innermost loop" can be a very misleading description! Besides that, other measures such as big-Omega should be referenced in any discussion of big-O. (I did enjoy Big-O the anime series though! /grin)

jonahx 1y ago
> Big-O isn't as relevant as it once was. Modern hardware includes mutithreading, piplining, numa, and complex caching. Some operations can take less than one CPU cycle and others can take hundreds, or exceptionally thousands of cycles. Big-O theory was invented precisely to be a measure of computation that is independent of such low-level details. In that sense it is timeless. And any (decent) presentation always includes appropriate caveats like "the constant C may be very relevant for 'smaller' N".
- wpollock 1y ago
  You're right. I didn't mean to imply that Big-O is useless. I'm reminded on an incident in the 1990s, when I was an instructor teaching C at the local telco, when a student showed me a (COBOL) program that had stumped his programming team. It would always hang their computer when it was run. What caught my eye was the main loop was nested seven levels deep, and each loop ran 50,000 iterations. Their computer wasn't hung, they only needed to wait a decade or so for the computation to finish! Big-O knowledge made the error obvious to me, and I added that to the curriculum for all programming courses I could.
  - namibj 1y ago
    (on the order of) 110 bits of brute-force isn't anywhere close to "a decade" especially if you aren't throwing severe parallelism at it. Edit: we're talking on the order of a million times the current age of the universe if you have a multi-GHz CPU and only take one cycle for each inner iteration.

curtisszmania 1y ago

[dead]

csk111165 1y ago

Awesome, how did you make those interactive code execution in that box??

bubblyworld 1y ago

If you work with asymptotic notations enough you realise they can often (loosely) be used like numbers - they obey certain arithmetic laws, and it's not uncommon for analysts to write stuff like 2^o(1), for instance. Take that rabbit hole further and you get the hyperreals! A number system that at once generalises real numbers, asymptotic notation and infinitesimal/infinite quantities =D https://en.m.wikipedia.org/wiki/Hyperreal_number https://en.m.wikipedia.org/wiki/Hyperreal_number (for anyone who cares, the ultrafilter construction kinda bakes in the laws of asymptotics into its definition of equality, if you squint)

pss314 1y ago

I found https://www.bigocheatsheet.com/ https://www.bigocheatsheet.com/ and https://visualgo.net/en https://visualgo.net/en helpful in the past.

nilsherzig 1y ago

Loving the interactive visualizations. Reminded me of https://kelseyc18.github.io/kademlia_vis https://kelseyc18.github.io/kademlia_vis Can someone recommend a collection of similar pages?

curious_gustaf 1y ago
https://explorabl.es/all https://explorabl.es/all

Beestie 1y ago

Late to the party but as a layperson who knows just enough about programming to be dangerous, I found the article to be enlightening. Never assumed that reading it would turn me into an expert at it. Never heard of big O till now but find it a fascinating way to look at algorithm construction. One more thing: if every article about everything has to be a flawless exhaustive explanation then I suppose only 13 people would even know about relativity. There is plenty of room for content that simply introduces an idea and leaves filling in the gaps to the reader's discretion.

the_af 1y ago
I think the criticism here is not that the article is incomplete ("not exhaustive") but rather that it makes several fundamental mistakes and doesn't actually describe Big O. It describes a "pop culture" version of Big O, which is not Big O, but calls it Big O. It's not useless, and a lot of care seems to have gone into it, but ultimately it's a lay person explaining something they don't firmly grasp, and making a couple of serious mistakes in the process. I love the presentation itself though!

clbrmbr 1y ago

I would have liked to see n log n

JohnKemeny 1y ago
n log n is a lot like n, in that if n less than a trillion, n log n is at most 40•n.

ChicagoDave 1y ago

I liked the presentation (right or wrong), but wanted to point out I’ve been in IT as a coder and architect for 40 years and never once needed to know big O notation. Which I think is the complaint here. The article author might have made an effort to connect it’s significance to Internet solutions like Search. I assume he didn’t because that’s already been done.

echelon 1y ago
Every engineer should be familiar with at least the basics of computational complexity. If you're stacking loops, you ought to know what that does. You also really ought to also what your core data structures are, how they work under the hood, and how the different operations on them consume space and time. If you don't familiarize yourself with at least those bare basics, you're doing yourself and your customers (and your future maintainers) a disservice.
- ChicagoDave 1y ago
  I’ve always done load tests, cured bad code, re-tested. Static analysis can discover most of these kinds of problems. It’s entirely possible I’ve been resolving big O problems intuitively over the years.
mock-possum 1y ago
fwiw I’ve been writing code for 2 years and I have occasionally benefitted from half-remembering the concepts that big O notation describes (even though my memory of the proper terminology is pretty shoddy, it’s been a long time since we covered it in college) When new releases of website features have resulted in notably poor performance, and profiling has revealed a particular function taking time on the order of seconds to complete (seconds are an eternity in UI land) it’s important to be able to reach into code that processes big chunks of data, and identify loops-within-loops-within-loops that could be rearchitected to play out more efficiently. Knowing that you’re going from O(n^2) to O(2n) is really just a matter of jargon - knowing that your list of results now displays in 1/10th the time, and why, is still pretty important. The underlying logic/math is the important bit to have a concept of, imo, big O is just a fun way to talking about it.

diffrinse 1y ago

In the example function that calls `indexOf` in a for..of loop, my mind went straight to the `join('\n')` when the newline delimiter could've been included in the string concatenation operation in the loop.