Hacker News Reader

You cannot talk about complexity without letting n-> infinity. Both algorithms are O(1), since n is bounded.

True, but I wanted to go with a simple example to show my point.

how is n bounded in the 2nd algorithm?

If you assume that it's unbounded, then either the algorithms aren't solving the same problem or the first one is wrong, so it doesn't make sense to compare them.

> For real world performance, benchmarking is the key.

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.

That's the point of O-notation though. It helps you know how your computation will degrade as your data grows.

So you start with benchmarking your current data. You still need to always think about how your data will grow.

> Only it's not enough.

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.

https://youtu.be/OPoZWnYIcP4?t=1035

> 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

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...

You seem to be agreeing with the parent comment's point. For example, there's this bit of their comment, which is almost verbatim what you replied back with:

> ... 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 data has changed and is now an order of magnitude larger

If your data changes, and you care about performance, then your data structures and algorithms should be reevaluated.

I would probably argue that either the first algorithm is incorrect (because searched can be larger than INT_MAX) or the complexity of the second algorithm is bound both by O(searched) (or sqrt(searched), if implemented with more vigour) and O(1) (because the value of 'searched' is bound by a constant).

I explicitly wrote

> 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.

It looks like you intended your first snippet to end with `return result` not `return i`, right?

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. :-)

I would have a huge problem describing the first one as O(1). Technically the complexity is min(searched, INT_MAX), but the algorithm would also fail to produce a result if it reaches INT_MAX.

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.

It takes the same (huge) amount of time for all inputs - there's no early exit it always scans to INT_MAX. Hence O(1)

This is incorrect. Putting a finite bound on n does not reduce n to 1. n is always meant to be a finite arbitrarily large value. n=INT_MAX qualifies as arbitrarily large, especially on a 64-bit system.

O(x) = O(1) if x is some finite constant.

There is no bound on n, it always searches to INT_MAX regardless of n.

Big-O notation says nothing about the overall absolute size. All that matters is how the amount of work scales with the input value.

If an algorithm will always take 1 billion years to complete regardless of the input, then it's still O(1).

Consider n=INT_MAX*2 or INT_MAX^2 though.

The behaviour does flatline as n approaches infinity

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.

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.

Question: is the first algorithm O(1) cause we treat INT_MAX as a constant, right?

Correct.