Hacker News Reader

Comment by carnitine | Hacker News Reader

That’s just not how complexity analysis works, if there’s a bound anywhere, it is O(1). The behaviour below that bound may be of more practical importance, but it’s not how O-notation works. The parent comment doesn’t make a great deal of sense for other reasons, but your objections don’t hold either.

View on HN

By this logic, all programs that we run are O(1), since any data structure is in practice bounded in size by your available address space (+ disk space if we want to be pedantic). So, you can replace any loop over the elements of a DS with a loop over all memory in the address space, and you will get an O(1) algorithm.

In the end, it's just not a useful way of modelling the problem.

Yes, so ordinarily we analyse an idealised algorithm running on idealised machine. However if an upper bound is clearly introduced to this idealised setting, as in the root comment, then it can’t be ignored.

So an idealised machine doesn't have an arbitrary INT_MAX limit. The algorithms are O(n).

But playing tricks with the INT_MAX limit ignores(or, more accurately, spits in the face of) the fact that we want our computers to pretend to be idealized machines.

Floats aren’t real numbers but we treat them like the mathematical object that they model for most purposes.

Of course, being aware of the limits of our models are important, but abusing the tragic finitness of our models to “well actually” someone is generally not helpful.

“The heat death of the universe will occur in finite time, therefore all algorithms you can ever use are O(1)” isn’t a very helpful metric.

Reply on news.ycombinator.com