Web development is about displaying ONE PAGE of data. 20 items. 40 items. 100 items. No more. A far cry from the thousands of items you say it requires (I'd argue that it's a lot more). And just so we're clear a supposed O(n^5) algorithm with n constant (like on paginated web pages), is really O(1).
The thing about O(n) algorithms versus O(n^2) algorithms is that very often rewriting an O(n^2) algorithm into an O(n) algorithm involves splitting the loops, and using way more memory.
And that's assuming you do it correctly. Mostly people don't. Example, your basic optimization of a double for loop turns into:
# (1)
x = {}
for e in lst:
x[e.field] = e
for e in lst:
e2 = x[e.value]
# do something with it
Is that x[e.field] is an allocation and takes O(n) time. So this is an O(n^2) loop, and you have saved nothing over this, even in theory
# (2)
for e in lst:
for e2 in lst:
if e2.field == e.value:
# inner loop
So in this obvious case it takes infinite items in theory. Even that is a wrong prediction. (2) will also behave very differently depending on whether the VM is just starting up or has been running for a while. So in practice here's what's going to be faster:
n 10000 and total size
Why, in the beginning not doing the setup is just faster by itself. This lasts a long time because when the inner loop executes in cache and the hashtable copy does not fit in cache the loop is 100 times faster (on top of that ~100 times C acceleration). This means the loop stays fast for a long time.
Needless to say, this means that for anything you should do client-side the double loop will be the faster option, even on the slowest mobile cpu any of your customers might use.
At some point the Hash table will start winning. Until it causes virtual memory activity during the lookups. At which point, it's memory usage makes it useless. I'll see about actually running this test with an actual example program.
Hence, it's good to keep Rob Pike's rules of programming into account: http://users.ece.utexas.edu/~adnan/pike.html
Rule 2. Measure. Don't tune for speed until you've measured, and even then don't unless one part of the code overwhelms the rest.
Rule 3. Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, don't get fancy. (Even if n does get big, use Rule 2 first.)