Array access is O(1) implies a fixed index size, which implies O(1) array traversal?

Question

Arrays are generally presented as data structures with $\Theta(N)$ traversal and $\Theta(1)$ random element access. However, this seems inconsistent:

• if array access is really $\Theta(1)$, this means that the size of an element index is bounded by a constant (e.g., int64), since it can be processed in $\Theta(1)$. However, this implies that the array size is bounded by a constant (e.g., 2⁶⁴ elements), which makes traversal $\Theta(1)$.

• If traversal is $\Theta(N)$, then the size of the index has an information theoretic lower bound of $\Theta(\log N)$. Accessing an arbitrary $k$-th element requires processing the entire integer k, which has $\Omega(\log N)$ worst-case time-complexity (as $k$ can be arbitrary large).

In which model can both "standard complexities" defined for arrays, $\Theta(N)$ traversal and $\Theta(1)$ access simultaneously be true without the model being inconsistent?

Answer 1

It's a good question. From a pragmatic perspective, we tend not to worry about it.

From a theoretical perspective, see the transdichotomous model. In particular, a standard assumption is that there is some integer $M$ that is large enough (i.e., larger than the input size; larger than the maximum size of memory needed), and then we assume that each word of memory can store $\lg M$ bits, and we assume that each memory access takes $O(1)$ time.

Notice how this solves your paradox. In particular, we'll have $N \le M$, so there is enough space in the array to store the entire array. Also, each array access really does take $O(1)$ time. The solution here is that $M$ grows with the size of the array, and is not a single fixed constant.

You can think of the transdichotomous model as assuming that we'll build a machine that is large enough to handle the data we're processing. Of course, the larger the data you have, the more bits you need to have in the address, so we need a wider bus to memory, so the cost grows -- but we just "ignore" this or assume it grows as needed.

There is a sense in which this model is cheating a little bit. While the time complexity of a memory fixed is $O(1)$ (fixed, independent of $N$ or $M$), the dollar cost of the computer does grow with $N$ or $M$: to handle a larger value of $M$, we need a larger data bus to memory, so the computer costs more. So there is a sense in which the transdichotomous model is cheating, and the cost of such a computer will go up as $\Theta(M \log M)$, not as $\Theta(M)$. In effect, the transdichotomous model is assuming we use increasing amounts of parallelism as the size of our data grows. You could argue that it is realistic, or that it is "sweeping under the rug" the cost of increasing the size of data buses, etc. I think both viewpoints have some validity.

This is analogous to how we think about Turing machines as a reasonable model for everyday computers. Of course, any one computer has a fixed amount of memory, so in principle we could say that it is a finite-state machine (with a gigantic but fixed number of possible states), so it can only accept a regular language, not all decidable languages. But that isn't a very useful viewpoint. A way out of that is to assume that when our computer runs out of storage, we go out and buy more hard drives, as many as are needed, to store the data we are working with, so its amount of memory is unlimited, and thus a Turing machine is a good model. A pragmatic answer is that Turing machines are closer to every computer than finite automata.

Answer 2

Big-O notation can be tricky because it hides details. Big-O describes a way to measure a function related to complexity. That function may be "number of memory accesses," which would explain the O(1) complexity. However, if you were on a machine supporting large heterogenous memory spaces, that may hide a complexity that you cared about. For example, on a NUMA supercomputer, with hypercube interconnects, we find that array access requires O(log n) network transactions, even though it's only O(1) memory accesses. This is because each memory access may requires some logarithmic number of steps to reach the node that has that memory.

It is up to the developer/theorist doing the work to determine whether any given metric is the "right" metric for the problem. And it can be easy to get them wrong.

In your specific case, I would assume that I have an oracle that can de reference a memory address to its value, and measure how many oracle accesses I need to do any given operation. I like using oracles like this because they're a big honkin' red flag. They encourage scrutiny. The question of "is this measuring what I want to measure" comes naturally from their use. And, in many circumstances, we find that this model is acceptable for most architectures. In particular, if you have more than 18 exabytes of memory (at which point the 64-bit addressing model falls apart), you should question this assumption. Under that number, its a reasonable model, especially when we recognize how much of it is handled in parallel by the hardware and electromagnetic physics.

Remember that Big-O is an asymptotic complexity number, measuring behavior as your values approach infinity. You will never actually operate on machines with infinite memory space, nor infinite processing time. In the practical world, we use it as a surrogate for measuring the actual complexity as actual complexity can be nefariously difficult to compute.

I recommend anyone who has gotten the basics of Big-O and wonders about the dark corners of its assumptions to look at matrix multiplication. There's a rather obvious $\Theta(n^3)$ algorithm that's pretty easy to get to, but there are faster ones. Strassen's algorithm reaches $O(n^{\log_2 7}) \approx O(n^{2.807})$. There are even faster algorithms, in theory. However we start to find that the Big-O notation lies for our smaller finite problems. The time constants on the faster algorithms are hard to stomach, so it is rare to find anything faster than Strassen's is value-added.

But, for many many algorithms, Big-O does a good job of describing things. For lots of things, its very obvious that a $O(n^2)$ algorithm is notably slower than a $O(n \log n)$ algorithm for reasonably sized $n$. Often no more than a thousand is needed. We rarely push the limits of the size of our integers, except perhaps once per generation.

But, when you get to the big numbers, it is indeed worth revisiting the notation, and asking whether it is really measuring what you seek.

Answer 3

The cost of array access would be for example $c_1$ if the array size is less than $2^{64}$, $c_2$ if the array size is less than $2^{128}$, $c_3$ if the array size is less than $2^{256}$ and so on. Since $2^{128}$ exceeds the total size of all hard drives on earth, and $2^{256}$ vastly exceeds the number of bits that can be physically stored in the universe, we are justified to ignore that array access doesn't take constant time.

We are not justified to ignore that accessing all elements in an array of $2^{64}$ items takes an awful lot longer than accessing all elements in an array of ten items. There is a large gap between computer science being abstract and not caring about implementation details, and having only results that are basically useless.