A visual introduction to big O notation

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.

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?

n^2 algorithms on _massive_ inputs seems a little far fetched, no?

Around one to one hundred billion things start getting difficult.

n^2 is probably the worst offender of these algorithms - it's fast enough to get into production and slow enough to blow up once you start using it.

Rockstar infamously wasted five minutes loading GTAV because they had an n^2 algorithm in the startup sequence.

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

> true obviously

Well, it doesn't seem that obvious, at least not to everyone, because several times I've seen people rewrite things to make it O(1) when it was actually slower for the vast majority of cases (or even all cases).

Even if it's slower for the vast majority of cases, but there are rare cases where the computer would otherwise freeze, that's still a win.

Your computer will not freeze if your input is small enough no matter what big-O says. In many cases it's guaranteed to be small or small-ish.

N^2 is just two nested loops. It trivially shows up everywhere you have 2D arrays.

Do I really need to make my code spaghetti if the array sizes are small enough to not impact my speed ?

if you can guarantee N is small, then it’s probably not an issue.

Iterating over a 2D array using nested loops is an O(N) operation. N is the size of your data, how it's represented in an array is irrelevant.

> In many cases it's guaranteed to be small or small-ish.

And in many cases it's assumed to be small, but not guaranteed. That's where the trouble lies.

A classic example is Windows using a quadratic algorithm for arranging desktop icons that caused severe performance issues when users had many icons on their desktop.

https://github.com/microsoft/Windows-Dev-Performance/issues/...

I'd argue that one billion is fairly large for what most people work on. But yes, point taken.

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