> On a 64-bit CPU, y=x+1 is O(1) time when Y < 2^64, but becomes O(log N) time for larger numbers.
I thought that big-O does not actually consider the underlying hardware. How can you specify the CPU model / instruction conditions and still use the semantics of big-O analysis? The mathematical definition of O(_) does not involve hardware, it implies that there exists some coefficients and a constant. I get the point you are making but is big-O an appropriate way of measuring in this context?
As far as I know, big O notation definitely requires that we define the model of computation model we're using and the operations that this model can perform in constant time. Usually that definition is not made explicit or rigorous.
When say that comparison sort is O(n * lg n), we're assuming a computational model where comparing two integers is a constant time operation. That's true in most physical computers when we use the CPU's comparison instructions. It's also true in any theoretical model where we define a (finite) largest possible integer. So it works well enough.
You are using O(n) to measure the actual performance of an algorithm in practice. This is not the intention of O(n) -- rather it is used to classify functions into groups depending on "how they grow" with respect to the input as it goes to infinity. This is good because different instructions, or sequences of instructions, will perform differently across CPU architectures, for example two CPUs might have different cycles-per-instruction. Big-O makes claims independent of the hardware that remain true forever. Just because algorithm A is O(n) and B is O(n^2) does not mean that A will always outperform B.
I’m not conflating big O notation with benchmarking. My point applies to theoretical models of computation.
I’m pointing out that, for example, comparison sort is only O(n * lg n) in theory if the theoretical model of computation we’re dealing with can compare any two items in constant time. Comparing arbitrarily large integers can not be done in constant time in theory, so if that’s the problem we’re discussing then the complexity will not be O(n * lg n). But again, we generally are implicitly concerned with models of computation where comparison is a constant time operation.
Yes, Big O notation measures asymptotic growth of functions. But what do those functions express? For them to express running times, you need to define a machine model. It's a model because it's not a real machine – we don't stroll into a computer shop and pick up some computer and use that as our reference. Instead, we define an abstract machine model. Often, that's the word RAM model which assumes that for an input size n, the machine can process words of size θ(log n) in constant time. This is reasonable close to how our actual computers work: 64-bit words, and we can do stuff with them in constant time. But it's not perfect, because the RAM model doesn't have any caches (let alone multiple levels of cache hierarchy), doesn't have disks, doesn't model the paging system, etc. If any of these things are of significant concern to you, pick a different model (e.g. an external-memory model to consider memory hierarchy, or look into cache-oblivious algorithms, ...).
But talking about asymptotic running time without specifying which model you're using is absolutely pointless.
I don’t think that’s accurate. The length of a collection is not necessarily correlated to the largeness of its largest element. The n in comparison sort is indeed the length of the collection, and that’s the only variable we generally discuss because we generally assume some fixed maximum allowable element.
> is big-O an appropriate way of measuring in this context?
I don't have formal CS education. I'm less interested in math and more oriented towards practical aspects. Infinity doesn't exist in practice (except these IEEE float magic values), but we can reason about shape of functions, e.g. "count of executed machine instructions as a function of N".
Not the same thing as CS-defined big O, but close.
Can be useful to reason about complexity of algorithms. More precisely, about complexity of their implementations.
Usually useless to reason about time: a machine instruction takes variable time to run on a modern CPU, the same instruction can take less than 1 cycle or much more than 1M cycles.
The amount of memory needed to hold an integer is log(N). That's just because the log is about how many digits it has. That fact doesn't depend on the hardware, it's just a math fact.
There's generally an assumption that the elementary values we're using fit into native hardware values, and that some elementary operations on those values can be done in constant time (e.g. a CPU instruction).
If you want to talk about something like supporting arbitrarily large integers or defining the memory of the physical computer we're using, we need to be explicit about that, because it changes a lot of things. After all, a finite-memory computer is not Turing complete, and everything it can compute can be computed in constant time. :)
If I've read between the lines correctly, your point is that N bits allows you to represent 2^N values, but they don't have to be the values from 0 to 2^N.
I thought that big-O does not actually consider the underlying hardware. How can you specify the CPU model / instruction conditions and still use the semantics of big-O analysis? The mathematical definition of O(_) does not involve hardware, it implies that there exists some coefficients and a constant. I get the point you are making but is big-O an appropriate way of measuring in this context?