[b52_]

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?

[Panzer04]

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.

[svara]

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

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

Around one to one hundred billion things start getting difficult.

[vlovich123]

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

[b52_]

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