4 ms·

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

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

patrickthebold 7y ago
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.
- baddox 7y ago
  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. :)
- ouid 7y ago
  it's a little more complicated than that.
  - patrickthebold 7y ago
    how so?
    - ouid 7y ago
      well I can hold somewhat arbitrarily large integers in memory with the ackermann function, for instance.
      - slavik81 7y ago
        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.
        ouid 7y ago
        yes, sorry for being terse.
baddox 7y ago
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.
- ouid 7y ago
  typically the n refers to the length of the input. bigger numbers to compare gets cancelled out by the largerness of n.
  - baddox 7y ago
    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.
    - ouid 7y ago
      I am referring to the bit length of the input.
- TravHatesMe 7y ago
  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.
Const-me 7y ago
> 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.

patrickthebold 7y ago

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.

baddox 7y ago
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. :)
ouid 7y ago
it's a little more complicated than that.
- patrickthebold 7y ago
  how so?
  - ouid 7y ago
    well I can hold somewhat arbitrarily large integers in memory with the ackermann function, for instance.
    - slavik81 7y ago
      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.
      - ouid 7y ago
        yes, sorry for being terse.

baddox 7y ago

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.

ouid 7y ago
typically the n refers to the length of the input. bigger numbers to compare gets cancelled out by the largerness of n.
- baddox 7y ago
  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.
  - ouid 7y ago
    I am referring to the bit length of the input.
TravHatesMe 7y ago
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.

Const-me 7y ago

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