To put it another way, the constants inside a big-O are not really constant: they depend on what you assume is a constant-time operation.
The simple idea is that the most basic thing, that is reading the number "n" depends on the number of digits, so that's a log.
But in most algorithms, the "n" refers to the size of a data set. This set is usually stored in some kind of memory, and memory is a physical array of little cells in 3D space. Accessing that cell means travelling through the array, with a time to reach it proportional to its distance, and since capacity increases with the cube of the distance, the time it takes to get the data is proportional to the cube root of n.
The conclusion, to me, is that when complexity gets down to less than a cube root, mathematical abstractions start to break down and you need to consider the actual machine, in particular its cache architecture.
The amount of information at high enough amounts scales with the volume in which it is stored.
Because of the need to be able to reach the cells that store information, the density of information is normally high in 2 directions an low in the 3rd direction.
This is why it is useful to distinguish between the density of information per area, which is determined by things like the size of a magnetic head or the resolution of a photolithographic process, and the density of information per volume, which is determined by the density of information per area and by some kind of layer thickness, which is usually determined by mechanical considerations, e.g. to ensure enough strength for a tape or a disk or an integrated circuit package.
Like I have said, at high enough amounts of information you reach an almost constant information density per volume, like in a rack full with HDDs or in a magnetic tape robotic library.
The amount of information you are talking about is quite a bit lower than the amount I'm talking about. Big O is about limits, so if we're going to bring physical limitations into play to say there's some limit to density, you'd might as well go all the way. It's not limit as n -> 10^18; it's limit as n->infinity. You can't keep adding information and still get cubic scaling.
Ordinary memory is not a list. It's a flat space read in O(1).
In theory. In practice there are multiple levels of cache, and cached reads will be much, much faster than main memory reads.
So if your entire data structure lives in cache and you repeatedly loop through it, it's going to be processed much more quickly than a bigger and more spread-out structure.
There's also paging, and alloc/dealloc to consider, and maybe garbage collection.
By the time you include all of that big-O estimates can become wildly misleading generalisations, unless your n is always >a million or so.
For small n it can be way off.
Sequential reads from adjacent cells will be pipelined, so they can have a throughput that does not depend on the distance in address, but the latency to start another sequential read stream from a different address must depend on the address, for very big memories, e.g. of rack size, where the propagation from a corner of the rack to the other corner takes a long time in comparison with the memory clock.
And in the general case, memory reads do depend on distance. Hence:
> In practice there are multiple levels of cache, and cached reads will be much, much faster than main memory reads.
This is why we have the cache levels in the first place. And the hierarchy continues: L1, L2, RAM, block of spinning rust in the closet, "the cloud" somewhere... There is only so much storage you can fit close to core! More = physically bigger = physically further away.
Sure, within a level might feel like constant time. But that's because the optimal case for that level is slowed down to match the suboptimal cases. The step discontinuities in access time are caused by our inability to engineer a system to manage this tradeoff continuously, not a fundamental law.
If you build a computer with DRAM 10 cm away from the CPU and static RAM 50 cm away, access times for the static RAM will still be much lower than access times for the DRAM.
Why don't we just build all RAM as static? Because it's more expensive per bit, it uses more energy, and it requires a great deal more silicon area.
First, find a sufficiently large base b so that no intermediate calculation exceeds b-1 (one pass over the matrices should do the trick). Then encode each row of the left matrix as a big value A_i = sum_k a_ik * b^k. Encode each column of the the right matrix as B_j = sum_k b_kj * b^(n-k). Compute A and B explicitly (takes O(n^2) integer operations).
Now you extract the answer one element at a time. A_i * B_j has a bunch of terms including sum_k a_ik * b_kj * b^n. All other terms have different powers of b. So do an integer division by b^(n-1), discard the remainder, then take the result mod b, and that gives (a*b)_ij, costing one integer multiplication and two divmod operations per output element. Problem solved. Can I publish in FOCS?
This is, of course, a wild cheat: even with OpenAI’s latest and greatest galactic integer multiplication algorithm, this would be asymptotically slower than the plain high school matrix multiplication algorithm in any remotely realistic model of a computer.
I wonder whether the OpenAI papers contain cheats quite as outrageous as mine :)
(The moral here is that exact math is quite powerful, and exact math in time sublinear in the number of bits of precision is a great way to steal some performance.)