A Visual Introduction to Big O Notation
Original: A visual introduction to big O notation
Key topics
Regulars are buzzing about a fresh take on explaining big O notation, with commenters raving about the author's engaging visual introduction. The discussion reveals a common pitfall in explaining big O: glossing over the distinction between worst-case, average, and best-case scenarios. Commenters like IceDane and lordleft dive into the nuances, with umanwizard and bonoboTP clarifying that big O notation can describe any function's growth rate, not just worst-case runtime. The author, samwho, is receptive to feedback and is already considering how to incorporate these subtleties into the post.
Snapshot generated from the HN discussion
Discussion Activity
Very active discussionFirst comment
1d
Peak period
71
36-48h
Avg / period
22.9
Based on 160 loaded comments
Key moments
- 01Story posted
Aug 24, 2025 at 3:39 AM EDT
4 months ago
Step 01 - 02First comment
Aug 25, 2025 at 1:24 PM EDT
1d after posting
Step 02 - 03Peak activity
71 comments in 36-48h
Hottest window of the conversation
Step 03 - 04Latest activity
Aug 28, 2025 at 11:17 AM EDT
4 months ago
Step 04
Generating AI Summary...
Analyzing up to 500 comments to identify key contributors and discussion patterns
Want the full context?
Jump to the original sources
Read the primary article or dive into the live Hacker News thread when you're ready.
Me: 69
Webpage: "Nice'
---
Upvoted.
But seriously, this was really informative!
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.
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.
That section in particular has already seen several revisions based on other peoples’ comments.
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.
I feel like the way I have it is a reasonable, if strictly incorrect, simplification for someone new to the material.
When I write these, I have the newly-hired bootcamp grad as my target audience. Someone who has been taught the basics for how to write code for the web and work as a junior within a company, but has no computer science background. I want them to understand enough to make sense of what they see.
"It's common for an algorithm's performance to depend not just on the size of the input, but also its arrangement. In such cases we typically use big O notation to describe the worst-case scenario. However, note that we may perform similar analysis on the best case or the average case as well."
But here:
> 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).
This is plain false, the worst-case runtime of bubble sort is indeed Θ(n^2). Either delete it, or write about the upper bound / lower bound thing.
I'm struggling to understand how the part about big theta is false. Is the best case for bubble sort not O(n)? I've deleted the section for the time being.
You can talk about the big-O of the average case, the big-theta of the average case, the big-O of the worst case, or the big-theta of the worst case.
It is also the most sensible one. Best case version is basically useless, if you are lucky you may end up with O(1) but that doesn't tell you anything. Average case could be good but it requires you to estimate the distribution.
And then derive big-O in terms of such properties.
See for example Tetris-LoadBalanced and Tetris-Reordered (on top of Tetris-LoadBalanced) for such works: https://arxiv.org/abs/1909.12102
And I really do mean just a few years. Like, Joe Biden was President.
I’d be interested to hear how you would explain it when you’re at a more appropriate device.
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.
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.
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
> 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
For example: "the function x^2 is O(x^3)" is a valid sentence in big-O notation, and is true.
Big O is commonly used in other places besides analysis of algorithms, such as when truncating the higher-order terms in a Taylor series approximation.
Another example is in statistics and learning theory, where we see claims like "if we fit the model with N samples from the population, then the expected error is O(1/sqrt(N))." Notice the word expected - this is an average-case, not worst-case, analysis.
Using "always" is definitely wrong, but that isn't really what makes this wrong. BonoboTP caught another thing that I missed which tells me that you misunderstand some of these concepts on a somewhat fundamental level. Quote:
> 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).
Big O, Ω, and Θ are ways to describe asymptotic bounds on runtime. You can apply them in best, average, or worst case analyses. For example, linear search is O(1), Ω(1), and Θ(1) in the best case but it is O(n), Ω(n), and Θ(n) in the worst case.
> 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.
I'm sorry.. but what? You posted some learning material on the web which is wrong. I am just correcting you, and in a civil manner, mind you. I'm not exactly sure what you want me to do. Should we all just pretend that there aren't errors in what you posted so we don't hurt your feelings?
It's not clear to me based on what you're written what I should change. With the "always" wording changed, what else do I need to do for this to be correct? Ideally I want to avoid talking about asymptotic bounds.
HN (and forums) can be blunt in this way (cf. Cunningham's Law). When you put something up, most of the reaction will be about how it's wrong. Things being correct is just the default, people won't comment on how correct something is. Try to take it not personally and more like a helpful piece of info. Ideally you'd want all statements to be correct. Textbook authors often incentivize hardcore nitpicking by mentioning the submitters in the acknowledgments or even cash. Try to take it in that manner.
The O(g(n)) part says f is asymptotically bounded by g(n) up to some constant factor.
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).
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.
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 ;)
So I'd ding the candidate for poor communication.
As far as I know, and correct me if I'm wrong, there isn't a mathematical term for an approximate tight upper bound that's based off vague criteria of "fast enough".
In practice, people needed a way to say something like, let's not waste time getting all precise here, what's the approximate close-ish tight bound that's obvious, alright, that will work, let's use it.
Big Thetha implies proving the lower bound, and generally specifying the exact upper bound. So it was a worse term to use to describe the above, I think people settled on BigO, because you end up with some upper bound, and not necessarily the tightest one, but you lend on a tight-enough upper bound that it serves your practical purpose of choosing an algorithm to use in your application.
And so it became BigO, all for a lack of a better word, and eventually that became common parlance in those circles.
In every mathematical writing they come up with definitions to precisely describe this kind of things - that’s what the big oh/theta aim to do - formalize what we mean by “bounded by in long term growth”.
In practical software engineering, what is generally cared about is having a reasonable worst case upper bound. They don’t necessarily need the absolutely tightest bound, so you don’t need to spend extra effort chasing that. At the same time, they want to avoid bounds that are so loose they don’t give meaningful information.
That means the "upper bound" being asked for isn’t just about pure math. It requires applying practical judgment to the context we’re working in and the concerns we’re trying to address.
So yes, I’m asking for BigO, but with some flexibility. If you can provide the tightest bound, that’s great. If you can provide a tight enough bound that isn’t misleadingly loose, that also works.
A mathematician might cringe at words like "tight enough" and that’s fair. There’s no rigorous definition for it. But in the practical world where engineers are solving problems and users are paying for solutions, sometimes we need to rely on best judgment to land on a definition that serves the use case.
Because that's the prevalent need, BigO almost always implies the above in those context.
Have you studied math in an academic setting? The book “Art of Computer Programming” is all about formal definitions for understanding performance behavior.
> They don’t necessarily need the absolutely tightest bound,
Which is why I mention that big oh represents sets. But you dismissed that.
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.
The practical question is whether you think it's ok to continue propagating a rather crude and misunderstanding-prone idea about Big O. My stance is that we shouldn't: engineers are not business people or clients, they should understand what's happening not rely on misleading cartoon pictures of what's happening. I do not think you need a full-year collegiate course in calculus to get this understanding, but certainly you cannot get it if you fully obscure the calculus behind the idea (like this and uncountable numbers of blogpost explainers do).
First, software engineering doesn't just consist of Computer Science majors. We have a lot of people from accounting, physics, or people who have no degree at all. Teaching this concept in CS fixes very little.
Second, and complimentary to the first, is that asymptotic behavior is derivative of the lessons you learn in Calculus. You can't really full understand it beyond a facade unless you have a rudimentary understanding of Calculus. If you want to put this theory to the test then ask someone with a functional understanding of Big-O to write asymptotic notation for a moderately complex function.
I don't have a degree and in order to really understand asymptotics (and Big-O as well as the others) I read a primer on Calculus. It doesn't take a ton of knowledge or reading but a decent background is what will get you there. I do think we need a lot better continuing education in software that goes beyond O'Reilly style technical books that could fill this gap.
This seems to be quite a bit of a strawman to me.
ML is such a major part of the field today and at a minimum requires a fairly strong foundation in calc, linear algebra, and probability theory that I earnestly don't believe there are that many CS students who view calculus as "useless". I mean, anyone who has written some Pytorch has used calculus in a practical setting.
Now in pure software engineering you will find a lot of people who don't know calculus, but even then I'm not sure any would decry it as useless, they would just admit they're scared to learn it.
If anything, I'm a bit more horrified at how rapidly peoples understanding of things like the Theory of Computation seem to be vanishing. I've been shocked with how many CS grads I've talked to that don't really understand the relationship between regular languages and context free grammars, don't understand what 'non-determinism' means in the context of computability, etc.
Not really, if you ever listen to CS undergrads or people in non-traditional schooling (bootcamps, etc.) talk about software engineering this opinion is essentially ubiquitous. People interested in ML are less likely to hold this exact opinion, but they will hold qualitatively identical ones ("do you really need multivariable calculus/linear algebra to do ML?"). It is precisely because people (primarily Americans) are scared to learn mathematics that they rationalize away this fear by saying the necessary mathematics must not be essential, and indeed it is true that many people get away without knowing it.
It's probably unfair to qualify those as "computer science education" though...
I have no idea what's up with those disciplines, but it's an almost universal reaction to them. Unless people are very clearly and directly using them all the time, they just get dismissed.
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.
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.
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.
In computer science f(x) is often some complexity function, like number of some specific operations when running an algorithm to completion.
It definitely is not an "asshole" way of explaining it though.
Otherwise, we cannot say that 1 is O(x), for example.
In such cases as well, one might know for a specific application of the algorithm that, for example, `ρ` is bounded, and so the big-O becomes more influenced by the `n` and `K`.
Examples:
- algorithm with O(2^n) complexity might be faster for your problem than O(1) algorithm
- the same algorithm may be O(2^n) or O(n³) depending how you define size function
This is not straightforward.
Log(n) is unbounded, yes, but if a Turing machine halts in sub-linear time then there is some length input for which that TM halts before it reads every cell of the input tape. Therefore, it doesn’t matter how the size of the input grows, that TM must halt in constant time. Make sense?
What makes a/your TM special that this is the case?
I don’t mean to take too much of your time though, maybe I’m too dumb for this.
Edit: I can sort of see how O(log n) is impossible or at least O(n) in a TM, but to reduce it to O(1) makes no sense to me
Now consider any input I, and let I_N be the subset of I that fits in N characters (I.e. I_N is the same as I except with all characters past the Nth replaced by blanks).
Then by our earlier statement defining N, the TM must halt on I_N after fewer than N steps. But the TM’s behavior on I for the first N steps must be the same as its behavior on I_N, because it can’t possibly have read any different characters (since in N steps it can only have read at most the first N characters, and those two inputs are the same on that interval). Thus the machine must halt in less than N steps on I. But I was chosen arbitrarily, so we’ve shown that the machine halts in less than N steps on any input, and recall that N was a fixed constant.
I learned about Big O notation while learning calculus, along with little-o.
I took DSA as a third-year Electrical and Computer Engineering student. I recall maybe 15 minutes of exposition on the topic and exam questions of a near-throwaway nature (ergo: write this tree parsing algorithm, 95 points for your code's correctness, 5 points for explaining your algorithm's Big O complexity). It did seem like something that CS professors and teaching assistants considered either trivial or self-explanatory.
OK, so. So, it's like you mixed together Pacific Rim, Dark City and The Matrix all into the same show. In that order.
[0] https://nedbatchelder.com/text/bigo.html
[1] https://nedbatchelder.com/blog/201711/toxic_experts.html
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...
In reality, even regular subscribers probably aren't, and if you're a random visitor years later, the whole thing may be impossible to parse.
Because that's not what the article is about. It's not about whether Pyon was correct or wrong, it's that they were a dick about it. Their opening words were "you should be ashamed". They doubled and tripled down on their dickery later on.
And no matter how good your point is or how right you are: if you're a dick about it people will dislike you.
I'll double down on my toxicity by saying I didn't like the page layout. As someone with ADHD (and a declining memory), I need to be led through formatting/sub-headings/bullets/colored sections/etc into each detail or it all blends together into a wall of text. The longer it takes to make a point (visually and conceptually), the more lost I am. I couldn't easily follow it. The Simple Wikipedia page was more straight to the point (https://simple.wikipedia.org/wiki/Big_O_notation), but reading the "full" Wikipedia page thrusts you headlong into a lot of math, which to me signifies that this shit is more complex than it seems and simplifying it is probably a bad idea.
Ask yourself why. The usual answer is that top experts either can't be bothered to create better content, or they actively gatekeep, believing that their field must remain hard to learn and the riff-raff must be kept out.
I think the first step is to accept that laypeople can have legitimate interest in certain topics and deserve accessible content. The remedy to oversimplified explanations is to write something better - or begrudgingly accept the status quo and not put people down for attempts that don't meet your bar.
It's also good to ponder if the details we get worked up about actually matter. Outside the academia, approximately no one needs a precise, CS-theoretical definition of big-O notation. Practitioners use it in a looser sense.
This oversimplifies things.
It's sometimes a third option: the topic is complex enough it cannot be digested into a ready to consume blogpost without previous work (reading and practicing), which in turn requires previous work, and so on, until you've turned it into an introductory course.
And that's not gatekeeping or "cannot be bothered to simplify" -- it's a falsehood, a kind of internet new age mantra, that everything can be made simple enough to explain in a blog post. Some things can't. There's nothing elitist about it, since everyone has the mind power to take that introductory course.
> It's also good to ponder if the details we get worked up about actually matter. Outside the academia, approximately no one needs a precise, CS-theoretical definition of big-O notation. Practitioners use it in a looser sense.
The article made some genuinely serious mistakes and the author here (graciously, it has to be said) admitted to being wrong about some things like Big O being "the worst case".
In this cases, maybe the damage could be limited by saying "I know this isn't Big O, this is what some engineers call it but it's actually something different. Because practitioners find useful nonetheless, I will explain it (explanation follows)".
I found the visual presentation top-notch by the way, it's clear some effort was put into this and it shows!
Before asking why, ask if. There are good articles about complex topics, they just get drowned out by bad articles.
The thing I was taught wasn't wrong, but it left out important details. There are very specific steps involved in cleaning parts, applying the right lubricant, not applying lubricant, aligning parts, not forcing things, doing the same change on both sides, torque specs, bedding steps. If you don't do them, the brakes just fail again. The person who taught me didn't go over those important yet intricate details - probably because they were taught by a non-expert too.
If the choice is "quit my job to start writing lots of expert content", or "accept the status quo", I choose neither. I have my own life to live. But if during the course of living my life, a wave of inaccuracy begins to lap at my door, I will attempt to stem the tide, in my own way. The toxic aspect, I think, is really just the way in which these corrections are given, and definitely I and others could do better with our tone. But to just give up and not give the corrections at all, I think would be disastrous.
(fwiw, I think HN's overzealous "guidelines" force people to either be toxicly positive or insidiously critical. that's not to say I'm not an asshole, but it's hard to just be normal on this forum without this bizarre culture coming down on you)
It's a bit like the choice between two doctors. One is very polite, spends an hour by your bedside every day, smiles and holds your hand and encourages you not to give up but has no idea about how to interpret your symptoms, has a horribly confused idea of what's going on but can explain that mess in his head to you in a reassuring tone that feels authoritative.
The other doc is morose, doesn't smile, the meetings are brief like an interrogation but he knows exactly what's up, spends the time on reading the literature, case studies, phones up other doctors who treated similar illnesses, cuts you and sews you back at the right spot and hands you the exact pills that will get you on your feet in a few months, but at the same time was distant and cold throughout the whole thing and talked to you as if you were a car in the repairshop.
Ideally, it would be both. Of the two I'd still choose the second guy.
The more detail that’s included, the harder it becomes to write less. If you ask me to write 500 words on indexing strategies for an RDBMS, I’ll probably manage, but very little will be explained. If you ask me to write 5000 words, there’s no way I’ll hit that target, because I’ll want to explain every tangent, every fundamental, and so on.
The single best blog [series] that manages to pull this off, IMO, is Jeremy Cole’s series on InnoDB [0]. It’s not short taken as a whole, but each article is short enough that it (probably) meets people’s attention spans. I think the thing that makes it so great to me is that it’s written assuming that the reader already understands certain concepts. For example, he doesn’t spend multiple paragraphs explaining what a B+tree is; he links to the Wikipedia page, and then describes how InnoDB uses them.
In contrast, when I write something, I usually find myself assuming that the reader doesn’t have some fundamental knowledge. I usually try to either put it in a section that’s easily skipped, or in a pop-out toggle, but either way, it’s there.
To me, these fundamentals are incredibly important, because a. they’re how I understand things b. I don’t feel that you can operate something to its fullest capability (let alone fix it) if you don’t know how the thing works.
Re: gatekeeping, to me the perfect example is the Linux kernel. Torvalds is notoriously unfriendly, and while you can judge that however you’d like, the man has a massive weight on his shoulders, and letting code in that doesn’t meet his standards threatens that weight. I get it. Then, I also came of age during the RTFM era, so I’m used to it.
[0]: https://blog.jcole.us/innodb/
I bet you also have subjects where you use and spread inaccuracies unless you are universal expert
If you say, “hash maps are generally O(1), and are a great default choice,” you’re not that wrong (subjectivity aside).
If you say, “storing integers as strings guarantees precision, so you should prefer them over decimal or float types,” you’re technically correct about the first part, but are enormously wrong for a variety of reasons about the conclusion.
Don't think the entire internet is repeating inaccuracies. :) I also believe there are readers that attempt to learn further than a blog. A blog post can inspire you to learn more about a topic, speaking from personal experience.
If there were no blog posts, maybe there would be no HN I believe.
There should be a place for non-experts. One could remain skeptical when they read blog posts without hating blog posts about complex topics written by non-expert.
I hate that this declaration is both hilarious and one many might suggest I need to prefix with regularly.
:-D
Where it falls short is the usefulness to others.
My experience is the opposite. I hate the colorful books with many little boxes, pictures with captions in floaters, several different font sizes on the page, cute mascots etc, where even the order or reading is unclear.
Instead I found it much easier to learn from old books made before the 70s-80s, sometimes back into the 40s. It's single column, black on white, but the text is written by a real character and is far from dry. I had such a book on probability and it had a chapter on the philosophical interpretations of probability, which took the reader seriously, and not by heaping dry definitions but with an opinionated throughline through the history of it. I like that much better than the mealy mouthed, committee-written monstrosity that masks any passion for the subject. I'd rather take a half page definition or precise statement of a theorem where I have to check every word but I can then trust every word, over vague handwavy explanations. Often these modern books entirely withhold the formal definitions so you're left in a vague uneasy feeling where you kind of get it, have questions but can't find out "is it now this way, or that way, precisely?". And I'm not so sure that these irrelevant-cute-pics-everywhere books are really better for ADHD at the end of the day, as opposed to distraction free black on white paragraphs written by a single author with something to say.
HN is not an audience of laypeople (mostly) and will critique the article with a different mindset than a novice that might be impressed by the visuals (which are impressive).
So I think the reaction is both to be expected and reasonable: HN will critique how correct the explanation is, and point out the mistakes. And there were a couple of fundamental mistakes due to the author not being a subject matter expert.
The wrong take from this would be "... and therefore, technical details don't matter and it's ok to be inaccurate."
Besides, often you're lucky and there's a trivial perfect hash like modulo.
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?
Around one to one hundred billion things start getting difficult.
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).
33 more comments available on Hacker News