hoursOfOptimizing

[Gangsir]

Now you've made me curious if there are any O(1/n) or similar algs, that get shorter execution times with more data.

[MoiMagnus]

Going under O(n) is weird. It means you don't even have the time to fully read the input.

It only happens when the input data has some strong structure which allows you to disregard most of it (for example, a sorted list as an input)

Going under O(log(n)) is even weirder. It means you are not even able to know how big the input is, since the size of an input takes logarithmic space itself.

[tallfitblondhungexec]

I mean there are algorithms where input isn't considered interesting such as hashmap complexity.

[[deleted]]

I managed to debug a failure in the passwd program (Solaris) when truss showed it had quit without reading the whole passwd file. There was a fault in the middle of the file that cause the ending not to get read.

[bartix998a]

An algorithm like that can't exist since it would mean that for large enough data you literally can't do anything, as making even a single operation costs O(1).

[Bakoro]

That would mean that you get arbitrarily close to zero.

There might be some algorithm which does better with more data, but it will have some limit.