A visual introduction to big O notation

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.

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.

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.

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)

And to add to my other comment, I don't think it came to mean that out of stupidity either.

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.

> there isn't a mathematical term for an approximate tight upper bound that's based off vague criteria of "fast enough"

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

I don’t think it’s really possible to give a precise mathematical definition of "good enough for my use case."

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.