23
$\begingroup$

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., 264 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?

$\endgroup$
9
  • 5
    $\begingroup$ Take a look at the logarithmic cost model and at the word RAM model, you seem to be mixing the two. In the RAM model the word size is usually assumed to be $\Theta(\log n)$. In this model an array with $n$ element provides constant-time random access to the elements, and hence it can be "traversed" in $O(n)$ time. (Notice that integers up to $n$ fit in a single [or constant number of] memory word[s]). Some links: Cost models, Word RAM. $\endgroup$
    – Steven
    Jun 23 at 23:53
  • 1
    $\begingroup$ $2^\text{num_bits}$ is $2^{\Omega(\log n)} = \Omega(n^c)$ for some $c>0$ in the word RAM model (and using multiple words it is $n^c$ for any constant $c$ of choice) so there is no contradiction. $\endgroup$
    – Steven
    Jun 24 at 0:56
  • 3
    $\begingroup$ I think you need to make a decision about whether you're in the world of theoretical computer science or the world of practical engineering. In the theoretical world, the fact that addressing of memory locations is O(1) is surely an axiom, which is justified because it's a reasonable approximation to the behaviour of real finite computer equipment. Of course in real life it's not true at all, because of complications like CPU caching. $\endgroup$ Jun 24 at 15:19
  • 1
    $\begingroup$ I understand why standard complexities are the way they are from a practical point of view, obviously. My question is about which model can be used to represent these complexities in a consistent way. Just saying "it's a reasonable approximation" doesn't cut it, I was looking for a formal rule, which @D.W. provided. $\endgroup$ Jun 24 at 22:58
  • 1
    $\begingroup$ @MichaelKay Of course this is a theoretical computer science question; this would have been obvious from the question body, had you read it. And caching has no effect on whether is memory access is O(1), as either is bounded-time. $\endgroup$ Jun 27 at 4:34

3 Answers 3

31
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ We can buy memory that is bigger and faster... Making memory access constant time :-) $\endgroup$
    – gnasher729
    Jun 24 at 11:11
  • 7
    $\begingroup$ As soon as we start talking about dollar costs, we're well away from any theoretical model. At that point we have to start considering that memory access time depends on the speed of light... $\endgroup$ Jun 24 at 15:24
  • 1
    $\begingroup$ @MichaelKay: Once you start getting into engineering concerns, cache could become a factor, too. But a fixed size cache can be effective for arbitrarily large memory sizes, depending on the algorithm and its locality; its capacity in words doesn't typically need to scale up as a proportion of total RAM size. A growing word size does mean cache has to scale, and also its tags have to scale. But in terms of access time, it's probably "only" a large constant factor, not changing the big-O complexity since a cache miss is still constant time. $\endgroup$ Jun 24 at 19:43
  • 5
    $\begingroup$ Another way of looking at it is that the complexity is not measuring "time", but the number of primitive operations required to execute the algorithm. In that case, yes, for a larger M the cost of a primitive operation is larger (either in time or in dollars) in proportion to the word size, because the primitive operations need to be more powerful (one operation needs to do work on more bits), but the number of primitive operations performed by the algorithm does not get larger in proportion to the word size. $\endgroup$
    – kaya3
    Jun 25 at 17:34
  • 1
    $\begingroup$ @PeterCordes: For a single cache, I'd agree with you. That's just going to be a constant factor. But consider that we often see layered caches - even small embedded systems regularly have 2 layers, PC typically have 3, and 4 layers of cache have been used. If we now consider the theoretical model in which the number of cache layers is related to log-memsize, with each layer exponentially bigger, then I suspect you're going to see a non-linear effect. $\endgroup$
    – MSalters
    Jun 27 at 7:07
5
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ Thanks, but I don't see how this answers my question at all. I was looking for a consistent computing model in which you can have O(1) array access and O(N) array traversal. The proper answer to my question is the transdichotomous model that D.W. linked. Your answer boils down to "you can assume you have such a model" (or "ignore the inconsistency"), which isn't helpful at all to answer my question. $\endgroup$ Jun 26 at 10:17
  • $\begingroup$ @AntoinePietri Fair enough, although I do think the message of "don't over-emphasize Big-O" is an important message that should appear on many questions regarding such notation. If nothing else, they serve as a warning to newcommers who find questions like this on Google. From a personal perspective, I have always found secondary effects like caching (and even error correction!) play a large role long before the log N behavior of integer addresses do, and that is rarely well captured in Big-O. $\endgroup$
    – Cort Ammon
    Jun 27 at 13:20
2
$\begingroup$

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.

$\endgroup$
7
  • 4
    $\begingroup$ I get that, this is obvious for practical use cases. My question is more about which formalism can you use to ignore one and not the other, while still remaining self-consistent, i.e., a formal rule for which costs you're allowed to discount. $\endgroup$ Jun 24 at 13:31
  • 1
    $\begingroup$ If you end up with a formalism that doesn’t give you any useful results, why would you bother? $\endgroup$
    – gnasher729
    Jun 24 at 20:37
  • 1
    $\begingroup$ Why wouldn't the formalism give me any useful results?! $\endgroup$ Jun 24 at 22:53
  • 2
    $\begingroup$ I don't want a model that gives me O(1) everywhere, I want a computing model that gives me O(1) for access and O(N) for traversal that is self-consistent. Re-read my question. Is your answer that we can always discard O(log N) complexities because they're small? If not, which ones are we allowed to discard? If you have a O(log log N) algorithm, is it actually a O(log N) algorithm? Without a proper model you're not providing the answers to these questions. The correct answer was already given by D.W.: in the Word RAM model, operations on log N bits are O(1). $\endgroup$ Jun 26 at 15:26
  • 2
    $\begingroup$ How is it absurd? If you don't understand it, that's a different problem. Someone apparently got it just fine and was able to answer it properly. $\endgroup$ Jun 26 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.