A visual introduction to big O notation

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.

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.

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.

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.

This is how you would explain it?

> 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

> 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

Thank you.

The definition of big O notation is pure math - there is nothing specific to analysis of algorithms.

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.

> 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.

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 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.

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.

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).

No, I'm grateful for the time you're spending time helping me understand. I'm struggling to come up with wording that satisfies everyone and venting some frustration at you. I'm sorry, that wasn't fair of me.

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.

That framing really helps, thank you. <3

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.

Big O notation can be used to describe any function, whether worst case runtime of an algorithm, average case runtime of an algorithm, the price of eggs in China as a function of time, or anything else.

I should have probably been a lot more clear about who the target audience of my post was.

I would just say "almost always" to cut off the pedants. You do use the same notation to describe the best-case and average-case as well; people just don't care about those as often.

I did push up a rewording that hopefully lands better. Fingers crossed.

Pejoratively referring to people as "pedants" simply because they know what they are talking about is quite the ad hominem fallacy.

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