I think the issue here is that big-O notation is so often useful (i.e. an O(n^2 sorting algorithm will perform poorly in the real world) that we forget that the mathematical notion is, in fact, completely theoretical. We almost never encounter massive Cartesian products (n^p), and we do encounter power sets (2^n) so we live in a world where “polynomial == fast” is almost always true, even though “polynomial time” means nothing in the real world.
For example, let me introduce this function f : N -> N where:
f(n) = 2^2^n if n < 1000
f(n) = 2^2^1000 if n >= 1000.
I call this, “Crappy O(1)”, an homage to the Pretty Much Null Set. It’s O(1), but not in a way that matters. If that’s your runtime cost, then your function’s behavior is doubly-exponential until it outdoes the universe
Ergo, on a real specified machine, RAM access is O(1). It might be unacceptable O(1) relative to what’s possible with better hardware (more cache) and more efficient access patterns (software written by graybeards in R&D labs rather than Agile Scrum script-kiddies in open-plan offices) but it’s still O(1) a pop.
There is a theoretical issue here, but it’s not what most people have in mind, because it has little to do with real hardware. Namely, while both computers can “do the same stuff”, the Turing Machine is superior to a real-world machine in one way (infinite tape) that almost never matters but inferior (unless its internal state space is huge) in terms of random memory access– O(n) in the the distance between the head and the place to be written. In other words, real computers are practically better than Turing machines on the assumption of small (< 2^256) state spaces and symbol sets. Hence, a better model might be the RAM machine, which assumes memory access to be O(1). With a finite RAM machine, that’s fine. With an infinite RAM machine, it’s obviously unattainable at some point. Unless you have concurrent heads doing the work, you’re going to have O(n^1/3) cost with random access patterns, which makes your beautiful yottabyte sort routine actually O(n^4/3 * log n). Therefore, the infinite-memory RAM machine is, in fact, asymptotically superior to any computer that could be realized in the physical world (unless we discover access to at least countably many dimensions). Unlike the Turing machine, it’s superior to any real-world machine in a way that might conceivably matter. (The problem with the finite-memory RAM machine is that makes the mathematics more complicated, often for no good reason, because asymptotic space bounds typically tell us what we need to know there, and don’t rely on implementation details.) The infinite-RAM machine assumes an asymptotic bound that is physically impossible.
Why doesn’t this matter? I’d say that it’s probably because asymptotic bounds aren’t about the real world. They’re a mathematical construct (which is why it’s possible that P = NP but without admitting practical algorithms for NP-complete problems). After all, the distinction between polynomial n^167 and (sub)exponential n^(1 + (log log n)/100) where one is called “fast” and the other “slow” is the reverse of what we’d see in the real world. The reason why mathematicians care about “polynomial time” is that polynomials are a family of functions that are closed under composition: a 4th-degree polynomial of a 3rd-degree polynomial is a 12th-degree polynomial. This closure property is of very high theoretical importance, but matters little in the real world.
Likewise, one can debate endlessly the asymptotic performance of sorting. O(n log n) is the lower bound, right? Well, sort of. For arbitrary comparables, that is true. For, say, 32-bit (or 128-bit) integers, there are O(n) sorts that don’t use comparisons and are faster (time-memory tradeoff) like the radix sort. The hitch is that asymptotic bounds themselves become meaningless when we’re comparing over a domain that has only a finite number of possible values (e.g. 2^32 integers). Sorts become about counting rather than set management when n greatly exceeds the number of values. So is there a meaningful O(n) sort, given that these “O(n)” sorting algorithms operate on a set of (possibly very large) finite domain? And again, we find ourselves reminded that asymptotic bounds are really only about behavior while approaching infinity and that it’s somewhat by accident that they’re often informative of how to compute in the real world.
we live in a world where “polynomial == fast” is almost always true, even though “polynomial time” means nothing in the real world
Pulling out one part of a long comment, but while often true, I think less often than was once the case. There’s an old Alan Perlis quip, “for every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run”, and theorists have been getting a little more interested in characterizing how/when that might be the case.
The author seems a little confused about Big O notation. It’s a theoretical way of analyzing algorithm performance. By definition it ignores implementation details and machine specific details like memory, cache and instruction timing.
Obviously those details need to be considered when implementing an algorithm, but it’s irrelevant to the theoretical analysis because all algorithms will be affected in a similar way on a particular platform.
In this case, different architectures can have more or less (or even no) cache, and they won’t exhibit this behavior, which is why it’s left out of the theoretical analysis.
tl;dr an O(n) function is still slower than O(1) function at exactly the same ratio.
I think the issue here is that big-O notation is so often useful (i.e. an O(n^2 sorting algorithm will perform poorly in the real world) that we forget that the mathematical notion is, in fact, completely theoretical. We almost never encounter massive Cartesian products (n^p), and we do encounter power sets (2^n) so we live in a world where “polynomial == fast” is almost always true, even though “polynomial time” means nothing in the real world.
For example, let me introduce this function f : N -> N where:
f(n) = 2^2^n if n < 1000
f(n) = 2^2^1000 if n >= 1000.
I call this, “Crappy O(1)”, an homage to the Pretty Much Null Set. It’s O(1), but not in a way that matters. If that’s your runtime cost, then your function’s behavior is doubly-exponential until it outdoes the universe
Ergo, on a real specified machine, RAM access is O(1). It might be unacceptable O(1) relative to what’s possible with better hardware (more cache) and more efficient access patterns (software written by graybeards in R&D labs rather than Agile Scrum script-kiddies in open-plan offices) but it’s still O(1) a pop.
There is a theoretical issue here, but it’s not what most people have in mind, because it has little to do with real hardware. Namely, while both computers can “do the same stuff”, the Turing Machine is superior to a real-world machine in one way (infinite tape) that almost never matters but inferior (unless its internal state space is huge) in terms of random memory access– O(n) in the the distance between the head and the place to be written. In other words, real computers are practically better than Turing machines on the assumption of small (< 2^256) state spaces and symbol sets. Hence, a better model might be the RAM machine, which assumes memory access to be O(1). With a finite RAM machine, that’s fine. With an infinite RAM machine, it’s obviously unattainable at some point. Unless you have concurrent heads doing the work, you’re going to have O(n^1/3) cost with random access patterns, which makes your beautiful yottabyte sort routine actually O(n^4/3 * log n). Therefore, the infinite-memory RAM machine is, in fact, asymptotically superior to any computer that could be realized in the physical world (unless we discover access to at least countably many dimensions). Unlike the Turing machine, it’s superior to any real-world machine in a way that might conceivably matter. (The problem with the finite-memory RAM machine is that makes the mathematics more complicated, often for no good reason, because asymptotic space bounds typically tell us what we need to know there, and don’t rely on implementation details.) The infinite-RAM machine assumes an asymptotic bound that is physically impossible.
Why doesn’t this matter? I’d say that it’s probably because asymptotic bounds aren’t about the real world. They’re a mathematical construct (which is why it’s possible that P = NP but without admitting practical algorithms for NP-complete problems). After all, the distinction between polynomial n^167 and (sub)exponential n^(1 + (log log n)/100) where one is called “fast” and the other “slow” is the reverse of what we’d see in the real world. The reason why mathematicians care about “polynomial time” is that polynomials are a family of functions that are closed under composition: a 4th-degree polynomial of a 3rd-degree polynomial is a 12th-degree polynomial. This closure property is of very high theoretical importance, but matters little in the real world.
Likewise, one can debate endlessly the asymptotic performance of sorting. O(n log n) is the lower bound, right? Well, sort of. For arbitrary comparables, that is true. For, say, 32-bit (or 128-bit) integers, there are O(n) sorts that don’t use comparisons and are faster (time-memory tradeoff) like the radix sort. The hitch is that asymptotic bounds themselves become meaningless when we’re comparing over a domain that has only a finite number of possible values (e.g. 2^32 integers). Sorts become about counting rather than set management when n greatly exceeds the number of values. So is there a meaningful O(n) sort, given that these “O(n)” sorting algorithms operate on a set of (possibly very large) finite domain? And again, we find ourselves reminded that asymptotic bounds are really only about behavior while approaching infinity and that it’s somewhat by accident that they’re often informative of how to compute in the real world.
Pulling out one part of a long comment, but while often true, I think less often than was once the case. There’s an old Alan Perlis quip, “for every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run”, and theorists have been getting a little more interested in characterizing how/when that might be the case.
Author used the wrong definition of Big O then proceeded to use that in his justifications. I can’t help but laugh.
The author seems a little confused about Big O notation. It’s a theoretical way of analyzing algorithm performance. By definition it ignores implementation details and machine specific details like memory, cache and instruction timing.
Obviously those details need to be considered when implementing an algorithm, but it’s irrelevant to the theoretical analysis because all algorithms will be affected in a similar way on a particular platform.
In this case, different architectures can have more or less (or even no) cache, and they won’t exhibit this behavior, which is why it’s left out of the theoretical analysis.