[tjoff]

No? I'm tired and it was way too long since I dealed with Big O so someone will surely correct me.

Your computer being finite is irrelevant. Big O is about growth factor.

Just because you are capped at value X (< infinity) does not mean that every value below X has the same characteristics. If it did, sure, you are O(1). But if it is N^2 it will still be N^2 even if your machine only has resources for N < 12.

[kmill]

Big O is about the eventual behavior for large enough N. An algorithm is O(N^2) is for sufficiently large inputs the running time is < c * N^2, for some fixed constant c. That's a really weak guarantee for practical purposes -- it allows an algorithm to take stupidly long amounts of time on all practical inputs, so long as eventually it's got a running time with the given bound.

The colloquial use of big O as a general growth factor doesn't hold up to its definition, if you want to be sure it's valid for small inputs too.

I'm in agreement that saying algorithms on computers are all O(1) doesn't make much sense. In a finite memory model, it's impossible to solve big problems, so the running time function becomes undefined for big enough inputs, so big O becomes completely inappropriate in this situation.

[Dylan16807]

> I'm in agreement that saying algorithms on computers are all O(1) doesn't make much sense. In a finite memory model, it's impossible to solve big problems, so the running time function becomes undefined for big enough inputs, so big O becomes completely inappropriate in this situation.

The difference between "everything is O(1)" and "you're not allowed to use O" is pretty minor anyway.

Either way it takes a lot of very useful analysis and throws it out the window because a particular branch of math was being too pedantic about needing infinity.

Use big O anyway. It works fine. It's a good tool even within the limits of real machines. If you're not abusing it on purpose, it tells you useful information in the exact same way that the pure math version does.

[karmakaze]

> That I use Big O to analyze time and not operations is important.

This is why we have benchmarks and big-O for different things. If we care about cache level sizes and the constant factors, use benchmarks with increasing orders of magnitde.

Or if preferring to remain abstract, model N as the bits of memory so that the access cost goes up with increasing N. To represent specific cache level sizes and latencies use benchmarks everyone will understand.

[kmill]

I mean, big O comes from that particular branch of math. The whole point of it -- even in CS -- is it's asymptotic analysis. (It's also been long criticized in CS for this deficiency. Usually it's the hidden constant factor, but the minimum problem size before it's relevant is an issue too!)

It's fine colloquially misusing big O to mean something like "for usual inputs, the running time is roughly this function", but you can't then in the same breath say all practical algorithms are technically O(1), because that's just not true in the technical sense (and it's useless or at least inaccurate in the colloquial one).

It doesn't really matter, but to add more to the discussion, the way I see it is that computer programs are implementations of algorithms on some restricted set of inputs. The algorithm has the asymptotic analysis, but the program itself does not.

[Dylan16807]

> It's fine colloquially misusing big O to mean something like "for usual inputs, the running time is roughly this function", but you can't then in the same breath say all practical algorithms are technically O(1), because that's just not true in the technical sense (and it's useless or at least inaccurate in the colloquial one).

My argument is "there's no reason to stick to the exact technical definition, because the exact technical definition breaks when you apply it to real computers". I don't think that's contradictory in any way.

But I don't think this is a misuse either. Talking about "usual inputs" and "roughly" would be a misuse, sure. But if I can prove it uses at most an^2 + bn + c steps, and I call it O(n^2), then what's the problem?