Only it's not enough. When you benchmark an O(N^2) algo may seem fine but then three years later the data has changed and is now an order of magnitude larger. So you need not only know your data, you also need to spend time thinking about how large it can become.
> ... you might encounter cases where a quadratic complexity solution is completely fine, until you have a lot of data and then suddenly your code slows to a crawl [0]. That's why we need computational complexity ...
It seems like you're disagreeing only because you pulled out the one quote about benchmarking. But they were just saying that you need benchmarking to bootstrap the meaning of O(...) of an algorithm. That's the point that the original article missed, which is presumably why they described it as key.
The GTA Online loading screen bug is a recent example of this problem, with its in-game purchasable items growing larger over time: https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times...
True. But I do highly recommend watching Ben Deane's 2015 talk about testing Battle.net. In it he briefly touches upon benchmarks and estimating algorithmic complexity. It's somewhat difficult to suss-out the details of it. But the short version is basically to run the benchmark with a few different sizes and then estimate the complexity growth from that.
So you start with benchmarking your current data. You still need to always think about how your data will grow.
If your data changes, and you care about performance, then your data structures and algorithms should be reevaluated.
> to find the square root of an int:
so the value can't exceed INT_MAX :)
Overall, I know the two algorithms aren't perfect, but they're a simple minimal example to show the difference between complexity and runtime.
Mixing real-machine finitude with big-O theory often gives unexpected or unhelpful results. Once in an interview I argued that since hash tables have a finite number of buckets, at large enough scale they really have O(n) worse-case performance. That didn't go over very well. :-)
Functionally, though, I would describe this algorithm as O(N). It's just a straight up linear scan of the problem space. It's unbounded, with a worst case of O(Infinity) and no upper limit on what searched can be, but it's functionally O(N) regardless.
O(1) needs to basically be something like a hash key/pointer to memory address to get the result you're looking for. It will not increase linearly as the problem space increases, whereas your first example increases exactly linearly.
In the end, it's just not a useful way of modelling the problem.
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.
If an algorithm will always take 1 billion years to complete regardless of the input, then it's still O(1).
The behaviour does flatline as n approaches infinity
For real world performance, benchmarking is the key. Computers are very complex beasts and there are a lot of potential speedups or slowdowns you might never think of - memory bank order, thermal throttling and compiler optimizability can drastically change the results, just to name a few. Computational complexity is totally fine as an angle to find new possible optimizations, but in the end, you need to compare it to the other approaches and see what actually works.
[0] https://news.ycombinator.com/item?id=21743424