According to the exact literal meaning, every algorithm you ever run on your computer is O(1), because your computer is finite. The same can be applied to the reachable universe.
Context is inevitable.
Context is inevitable.
The article was specifically talking about putting algorithms onto real machines and the speed consequences. This creates a new version of the algorithm with certain limits. And because of these limits, there is a maximum runtime for any halting code, and it is a constant number.
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.
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.
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.
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.
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.
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?
Instead typically it's the amount of accesses into some array. Other times people get cute and it's `log2(input length)` so somebodies algorithm could be O(N) while if N was just `input length` then it'd be N^2.
So yes, your algorithm is bound by O(N^2), and that's the number that matters on practical computers... but it's also bound by O(1) with a stupidly large constant. So it's O(1).
> I guess you're the kind of guy that chooses to uses not 8-bit bytes in an interview?
Dude, I'm here specifically to argue against insisting on the exact literal meaning, and to choose the practical option.
But you're still saying O(sqrt(N)) in both of those. I think it's useful to use the term O(sqrt(N)). It's the best notation for the job.
Mechanical sympathy has little (if anything) to do with big-O, btw. LMAX, the poster child of mechanical sympathy, is really about minimizing the use of memory coherence machinery and not taking the substantial latency hits.