7 ms·

> isn't there quite a bit of a difference between O(1) and O(log N) space? On a 64-bit CPU, y=x+1 is O(1) time when Y < 2^64, but becomes O(log N) time for lar

> isn't there quite a bit of a difference between O(1) and O(log N) space? 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. With space it’s even more complex, sometimes for space saving it makes sense to keep less than 64 bits of these integers, i.e. it may become log(N) for much smaller values. For this reason, I’m not a bug fan of big O. Useful at job interviews. Probably useful for people working on extremely generic stuff like C++ STL which needs to scale both ways by many orders of magnitude, it’s not uncommon to have a vector with 1 element or 100M elements, the standard library must be good at both ends. But I don’t often solve such generic problems, I usually have some ideas how large my N-s are, and can act accordingly.

diabeetusman 7y ago
Let's say that our file consists of nothing but the new line character (1 byte). At 2^64 lines, that's 18.45 EB. Sure, for files larger than 18.45 EB at the minimum, computing the new line count will take O(log N) time. I'm all for nitpicking the issues with Big O notation, but this instance doesn't strike me as one.
- deleted 7y ago
  [deleted]
- OskarS 7y ago
  OP said “to be really precise, O(log n)”, to avoid nitpickers that might have added corrections. And it is absolutely true: to store the number N, you need O(log N) bits. That is how Big O notation works. The lesson to take away here is that O(log N) is REALLY REALLY small, for all sensible values of N. If an O(log N) algorithm is slow, it’s not because of the O(log N) part, it’s because of the hidden factors in O notation.
  - lorenzhs 7y ago
    > That is how Big O notation works. No it is not. "Big O" is a way of expressing asymptotic growth of some quantity, most often running time. But you need a machine model to even express running time. And sure, you can define your machine model to require O(log n) time for adding two numbers, but that's not particularly useful. In particular, the word RAM model—which is what is normally used—assumes a word size of θ(log n), and that basic operations on those words take a constant amount of time. We use models because otherwise even the simplest things would be impossible to analyse. Or do you want to include a three-level cache hierarchy, micro-op decoding, the paging system, branch mispredictions and memory timings in your complexity analysis? Why is it always the "bUt AdDinG tWo nuMbERs tAkeS O(log n) tImE" hill that HN commenters are willing to die on?
    - nothrabannosir 7y ago
      To be fair he did say O(1), and qualified the O(log N) with both parentheses and “to be really precise”. If you can’t be precise about the definition of O on HN, then where? (which, “to be really precise”, is a polynomial time tape based Turing machine, not a modern RAM machine with log N words. It’s pointless, but fun to remember :) )
      - lorenzhs 7y ago
        No no no! Big O has nothing to do with Turing machines at all! You can, of course, express the number of steps a single-tape deterministic Turing machine needs to solve some problem using Big O notation. But you can just as well express the number of Qubits that a quantum computer needs to solve some other problem in Big O notation. It has nothing to do with the quantity being measured. Are you perhaps mixing up the definition of complexity classes such as P and NP with Big O notation? First you need to settle on a model. Then you can express time, space, or some other quantity in that model using Big O notation. Arguably, I've found that HN is one of the worst places to be precise about Big O notation. Everyone here seems to think they know what it is, only to lay bare their misconceptions about it a second later.
    - OskarS 7y ago
      You're simply wrong here. The algorithm is O(log n), whether you agree to it or not. First of all, there's absolutely nothing that says that we have to assume that the number of lines is less than 2^64. Big O notation does not care what happens below that number, it only cares what happens when you go to infinity, which is a lot larger than 2^64. At that point you need arbitrarily sized integers, which are not fixed-space. Hence O(log n). Word size or RAM model does not matter one whit. This is how Big O notation works, it has nothing to do with practicality. As another example of a similar thing, consider Sorting Networks. The AKS sorting networks has the best "asymptotic depth" of any known sorting networks (O(n log n) depth, i think), but the hidden constants are so massive that there are no situations where the AKS networks are actually practical, for any reasonable input they are always beaten by other (asymptotically worse) networks. That doesn't mean that they "aren't O(n log n)" or whatever. Second: if we were to actually write this algorithm in the way which is most conservative with space, we wouldn't use a 64-bit integer in the first place. If we only care about memory, we'd start the count with a single-byte datatype (i.e. unsigned char) to keep the count. The algorithm now uses 1 byte of space. When that overflows (i.e. reaches 256 lines), we would change to a bigger data type, i.e. unsigned short. The algorithm now takes 2 bytes of data. When THAT overflows, we again promote the datatype to an unsigned int. Now we use 4 bytes of data. When that overflows, we finally promote it to a uint64_t. Now we're on 8 bytes of data. When that overflows... (etc.) See how the memory usage is growing? And how it's growing exactly with the logarithm of the number of lines? You're just wrong about this. Yes, you can absolutely say "assuming storage of all numbers is O(1), then the algorithm is O(1)" (essentially what OP said) but that is not a default assumption and it's not accurate to reality (since actually storing numbers requires O(log n) of space). And yes, branch prediction misses and cache misses are far more important factors here, but that doesn't change the fact that it uses O(log n) space. That's just simply true. Also: we're not dying on a hill. OP made an entirely accurate and true statement, which was met with an avalanche of people criticizing him using incorrect arguments and misunderstandings of Big O notation. We're just saying that he was correct all along.
TravHatesMe 7y ago
> 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.
naniwaduni 7y ago
everything that terminates is O(1) when you upper-bound the input size
lorenzhs 7y ago
> 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. No. Incrementing a 128-bit counter is also O(1) time on amd64/ARM8/... Only when your numbers are arbitrarily large would that become true. But that's why we use models that make clear what our assumptions are. In particular, the word RAM model (which is normally used to talk about sequential algorithms) assumes a word size of θ(log n), and that some basic operations on words (such as arithmetic) are possible in constant time. Models obviously have flaws (otherwise they wouldn't be models), but practitioners often make the mistake of overthinking them. How big, exactly, is your file that a constant number of 64-bit integers doesn't suffice? You can easily increment a 512-bit counter in constant time on an 8-bit Arduino. It doesn't matter whether I have to check one hypothetical 512-bit counter, 8 64-bit counters or 64 8-bit counters, it's a constant number and therefore O(1). Whenever this "Big O is useful for job interviews but not much else" sentiment comes up on HN, it's usually driven by a misunderstanding of what Big O and asymptotic analysis actually mean.
- Const-me 7y ago
  > Only when your numbers are arbitrarily large would that become true. Technically you’re right, I should have put “arbitrarily large” there, but assumed it’s obvious from the context. > but practitioners often make the mistake of overthinking them As an experienced practitioner, I happen to know how extremely inaccurate are these models. When I was inexperienced, the models helped more then they do now, after I have leared about NUMA, cache hierarchy, micro-ops fusion, MMU, prefetcher, DMA IO, interrupts, and more of these hairy implementation details. Before I knew all these things, heuristics based on asymptotic analysis were generally helpful. Now they’re less so, I sometimes deliberately pick an asymptotically slower algorithm or data structure because it’s faster in reality.
  - lorenzhs 7y ago
    Well yeah, for many problems, there are solutions that have wonderful running time in the RAM model, like van Emde Boas trees or Fibonacci heaps, but are approximately 100% useless in practice because of the constants involved. I guess this is where I pitch what we call "Algorithm Engineering", which considers both theoretical guarantees and practical performance, including properties of real-world hardware such as the ones you mentioned :) https://en.wikipedia.org/wiki/Algorithm_engineering https://en.wikipedia.org/wiki/Algorithm_engineering

diabeetusman 7y ago

Let's say that our file consists of nothing but the new line character (1 byte). At 2^64 lines, that's 18.45 EB. Sure, for files larger than 18.45 EB at the minimum, computing the new line count will take O(log N) time. I'm all for nitpicking the issues with Big O notation, but this instance doesn't strike me as one.

deleted 7y ago
[deleted]
OskarS 7y ago
OP said “to be really precise, O(log n)”, to avoid nitpickers that might have added corrections. And it is absolutely true: to store the number N, you need O(log N) bits. That is how Big O notation works. The lesson to take away here is that O(log N) is REALLY REALLY small, for all sensible values of N. If an O(log N) algorithm is slow, it’s not because of the O(log N) part, it’s because of the hidden factors in O notation.
- lorenzhs 7y ago
  > That is how Big O notation works. No it is not. "Big O" is a way of expressing asymptotic growth of some quantity, most often running time. But you need a machine model to even express running time. And sure, you can define your machine model to require O(log n) time for adding two numbers, but that's not particularly useful. In particular, the word RAM model—which is what is normally used—assumes a word size of θ(log n), and that basic operations on those words take a constant amount of time. We use models because otherwise even the simplest things would be impossible to analyse. Or do you want to include a three-level cache hierarchy, micro-op decoding, the paging system, branch mispredictions and memory timings in your complexity analysis? Why is it always the "bUt AdDinG tWo nuMbERs tAkeS O(log n) tImE" hill that HN commenters are willing to die on?
  - nothrabannosir 7y ago
    To be fair he did say O(1), and qualified the O(log N) with both parentheses and “to be really precise”. If you can’t be precise about the definition of O on HN, then where? (which, “to be really precise”, is a polynomial time tape based Turing machine, not a modern RAM machine with log N words. It’s pointless, but fun to remember :) )
    - lorenzhs 7y ago
      No no no! Big O has nothing to do with Turing machines at all! You can, of course, express the number of steps a single-tape deterministic Turing machine needs to solve some problem using Big O notation. But you can just as well express the number of Qubits that a quantum computer needs to solve some other problem in Big O notation. It has nothing to do with the quantity being measured. Are you perhaps mixing up the definition of complexity classes such as P and NP with Big O notation? First you need to settle on a model. Then you can express time, space, or some other quantity in that model using Big O notation. Arguably, I've found that HN is one of the worst places to be precise about Big O notation. Everyone here seems to think they know what it is, only to lay bare their misconceptions about it a second later.
  - OskarS 7y ago
    You're simply wrong here. The algorithm is O(log n), whether you agree to it or not. First of all, there's absolutely nothing that says that we have to assume that the number of lines is less than 2^64. Big O notation does not care what happens below that number, it only cares what happens when you go to infinity, which is a lot larger than 2^64. At that point you need arbitrarily sized integers, which are not fixed-space. Hence O(log n). Word size or RAM model does not matter one whit. This is how Big O notation works, it has nothing to do with practicality. As another example of a similar thing, consider Sorting Networks. The AKS sorting networks has the best "asymptotic depth" of any known sorting networks (O(n log n) depth, i think), but the hidden constants are so massive that there are no situations where the AKS networks are actually practical, for any reasonable input they are always beaten by other (asymptotically worse) networks. That doesn't mean that they "aren't O(n log n)" or whatever. Second: if we were to actually write this algorithm in the way which is most conservative with space, we wouldn't use a 64-bit integer in the first place. If we only care about memory, we'd start the count with a single-byte datatype (i.e. unsigned char) to keep the count. The algorithm now uses 1 byte of space. When that overflows (i.e. reaches 256 lines), we would change to a bigger data type, i.e. unsigned short. The algorithm now takes 2 bytes of data. When THAT overflows, we again promote the datatype to an unsigned int. Now we use 4 bytes of data. When that overflows, we finally promote it to a uint64_t. Now we're on 8 bytes of data. When that overflows... (etc.) See how the memory usage is growing? And how it's growing exactly with the logarithm of the number of lines? You're just wrong about this. Yes, you can absolutely say "assuming storage of all numbers is O(1), then the algorithm is O(1)" (essentially what OP said) but that is not a default assumption and it's not accurate to reality (since actually storing numbers requires O(log n) of space). And yes, branch prediction misses and cache misses are far more important factors here, but that doesn't change the fact that it uses O(log n) space. That's just simply true. Also: we're not dying on a hill. OP made an entirely accurate and true statement, which was met with an avalanche of people criticizing him using incorrect arguments and misunderstandings of Big O notation. We're just saying that he was correct all along.

TravHatesMe 7y ago

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

naniwaduni 7y ago

everything that terminates is O(1) when you upper-bound the input size

lorenzhs 7y ago

> 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. No. Incrementing a 128-bit counter is also O(1) time on amd64/ARM8/... Only when your numbers are arbitrarily large would that become true. But that's why we use models that make clear what our assumptions are. In particular, the word RAM model (which is normally used to talk about sequential algorithms) assumes a word size of θ(log n), and that some basic operations on words (such as arithmetic) are possible in constant time. Models obviously have flaws (otherwise they wouldn't be models), but practitioners often make the mistake of overthinking them. How big, exactly, is your file that a constant number of 64-bit integers doesn't suffice? You can easily increment a 512-bit counter in constant time on an 8-bit Arduino. It doesn't matter whether I have to check one hypothetical 512-bit counter, 8 64-bit counters or 64 8-bit counters, it's a constant number and therefore O(1). Whenever this "Big O is useful for job interviews but not much else" sentiment comes up on HN, it's usually driven by a misunderstanding of what Big O and asymptotic analysis actually mean.

Const-me 7y ago
> Only when your numbers are arbitrarily large would that become true. Technically you’re right, I should have put “arbitrarily large” there, but assumed it’s obvious from the context. > but practitioners often make the mistake of overthinking them As an experienced practitioner, I happen to know how extremely inaccurate are these models. When I was inexperienced, the models helped more then they do now, after I have leared about NUMA, cache hierarchy, micro-ops fusion, MMU, prefetcher, DMA IO, interrupts, and more of these hairy implementation details. Before I knew all these things, heuristics based on asymptotic analysis were generally helpful. Now they’re less so, I sometimes deliberately pick an asymptotically slower algorithm or data structure because it’s faster in reality.
- lorenzhs 7y ago
  Well yeah, for many problems, there are solutions that have wonderful running time in the RAM model, like van Emde Boas trees or Fibonacci heaps, but are approximately 100% useless in practice because of the constants involved. I guess this is where I pitch what we call "Algorithm Engineering", which considers both theoretical guarantees and practical performance, including properties of real-world hardware such as the ones you mentioned :) https://en.wikipedia.org/wiki/Algorithm_engineering https://en.wikipedia.org/wiki/Algorithm_engineering