That said, "time complexity" is a bit of a misnomer anyway. It's often implied, but underneath, there is a specific operation. For example, when we say that merge sort is O(N lg N), we mean in number of comparison operations.
My googling dug up [1], but I'm not sure if that's it or not.
My university schooling was pretty straightforward about memory access not being O(1). We also went over adding two numbers together (also not O(1)), but these are just generally elided for brevity's sake; I don't think most of us want to start worrying/optimizing for CPU caches prior to it being a thing that perf testing says we need to worry about.
> 16/32 bit pointers for small arrays?
It's not about the size of the array, it's about the location in memory. If you're storing an index, then sure, knock yourself out.
[1]: http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
¹I'm a software engineer, not a physicist.
Conversational Big O tends to include a lot of spherical cows (https://en.wikipedia.org/wiki/Spherical_cow), because when Big O comes up in conversation, people are more likely to be talking in generalities about high level designs. More detail could be counterproductive in that context.
When someone is actually trying to quantify and predict performance of an algorithm, then the other extreme becomes desirable- the more detailed and specific the function, the better.
With respect to the space problem, for some problems researchers don't care about it so much because it only means that it is a polynomial factor slower. For problems where the degree of the polynomial is important, theorists typically work with variants of Turing machines and need to specify which variant they are using, which typically do not allow random access, so this does not become important. Of course, random-access Turing machines are also studied that violate the physical constraint you mentioned.
(Hard to argue that this is related to big-O since there are only two data points, but I'm just pointing out that index size is in fact a real-world concern).
1. they are all fixed or bounded quantities;
2. all algorithms are subject to them.
On the other hand, in practice, the input size is also bounded. You deal not with arbitrarily long arrays, for example, since memory is not infinite.
So, I think, asymptotic time complexity is meaningful as long as the inputs we are considering can grow so much -- while remaining bounded -- that a linearithmic algorithm indeed outperforms, say, a quadratic one for a large and relevant class of inputs.
And that may be why computational models make those assumptions; but I'm not remotely sure.
Every theoretical model I've ever seen says that indexing into n bits of memory takes O(1) time. That's obviously impossible:
- The pointer you need to read is log(n) bits.
- The physical memory is at best O(n^(1/3)) distance away from the CPU, and thus takes that much time to get back to you. In reality it's probably O(n^(1/2)) because we build on flat planes (once you start talking about petabytes of data anyways).
Maybe this doesn't matter in practice, because the constants associated with these are small enough (but are they, how many memory/disk bound applications are there? How much extra performance could we squeeze out by using 16/32 bit pointers for small arrays?). It certainly doesn't matter in theory where things work like we say they do regardless of the physical reality. But it annoys me that it's so obviously wrong.