32
$\begingroup$

I’m not even a CS student, so this might be a stupid question, but please bear with me...

In the pre-computer era, we can only implement an array data structure with something like an array of drawers. Since one have to locate the drawer with corresponding index before extracting the value from it, the time complexity of array lookup is $O(log(n))$, assuming binary search.

However, the invention of computers made a big difference. Modern computers can read from their RAM so fast that we now consider the time complexity of array lookup to be $O(1)$ (even it’s technically not the case, because it takes more time to move the register over a greater distance, etc)

Another example is Python dictionaries. While one might get a dictionary access complexity of $O(n)$ with an ill-written overloaded __hash__ magic method (or ridiculously bad luck, i.e. keys having lots of hash collisions), it’s usually presumed to be $O(1)$. In this case, time complexity depends on both the hash table implementation of Python dictionaries, and the keys’ implementation of the hash functions.

Does this imply that hardware/implementation can affect the time complexity of algorithms? (While both examples are about data structures instead of algorithms, the latter are built on the former, and I've never heard of time complexity of data structures, so I'm using the term "algorithms" here)

To me, algorithms are abstract and conceptual, whose properties like time/space complexity shouldn’t be affected by whether they’re implemented in a specific way, but are they?

Improve this question
$\endgroup$
1

3 Answers 3

Reset to default
44
$\begingroup$

Sure. Certainly. Here's how to reconcile your discomfort.

When we analyze the running time of algorithms, we do it with respect to a particular model of computation. The model of computation specifies things like the time it takes to perform each basic operation (is an array lookup $O(\log n)$ time or $O(1)$ time?). The running time of the algorithm might depend on the model of computation.

Once you've picked a model of computation, the analysis of the algorithm is a purely abstract, conceptual, mathematical exercise that no longer depends on hardware.

However, in practice we usually want to pick a model of computation that reflects the reality of our hardware -- at least to a reasonable degree. So, if hardware changes, we might decide to analyze our algorithms under a different model of computation that is more appropriate to the new hardware. That is how the hardware can affect the running time.

The reason this is non-obvious is because, in introductory classes, we often don't talk about the model of computation. We just implicitly make some assumptions, without ever making them explicit. That's reasonable, for pedagogical purposes, but it has a cost -- it hides away this aspect of the analysis. Now you know.

Improve this answer
$\endgroup$
9
  • $\begingroup$ As you said, we use the random access model as model of computation but when we use GPU for certain calculations the time complexity for some algorithms changes as it uses the SIMD instructions. $\endgroup$
    – Deep Joshi
    Commented Jun 21, 2018 at 6:04
  • 6
    $\begingroup$ Also note that O() notation is an upper bound. Even if you use the drawer analogy finding a drawer in a limited size (real memory is limited in size) building takes O(1) time. Even if it takes you 20 minutes to reach the furthest drawer (all cache misses and you even have to load the data from swap) that is still O(1) time because 20 minutes will be your hidden constant for accessing memory. $\endgroup$
    – Goswin von Brederlow
    Commented Jun 21, 2018 at 14:51
  • 2
    $\begingroup$ For a real life example of what @GoswinvonBrederlow is saying, consider that searching for a value with a hash map is effectively $O(1)$. Searching for a value in an unordered array is $O(n)$. However, in a real application I wrote recently, using an array was faster than using a hash map. It was faster because I had a small number of values to search (less than 10), and the overhead of doing the hash and the hashmap algorithm was actually greater than the cost of just brute forcing the array-search! For practical sized problems, I sped my code up by a factor of 3 this way. $\endgroup$
    – Cort Ammon
    Commented Jun 21, 2018 at 15:16
  • 1
    $\begingroup$ @CortAmmon: Even on a large array, using linear search may be faster than using a hash map if all but a few of the elements on is searching for are very near the start. For example, if 50% of the elements match the first element, 25% match the second, 12.5% match the third, etc. except that one oddball element will match something that might be anywhere in the array, the expected number of comparisons to perform M lookups on a list of size N would be 2M+N. $\endgroup$
    – supercat
    Commented Jun 21, 2018 at 18:42
  • 5
    $\begingroup$ @DeepJoshi SIMD instructions don't change the complexity of algorithms. They only change the multiplicative constant. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Jun 21, 2018 at 19:49
5
$\begingroup$

I think there's a fundamental misunderstanding in the question. You compare a person finding an object in a sorted list (e.g., a specific page in a book, given its number) with a computer looking up an item from an array.

The reason that the former takes time $O(\log n)$ and the latter takes time $O(1)$ is not that the computer is so fast that it can do the binary search in the blink of an eye. Rather, it's because the computer doesn't use binary search at all. The computer has a mechanism to directly retrieve items from the array without searching. To retrieve the contents of an array cell, the computer just tells the memory controller the analog of "Give me page seventeen", the memory controller sets the voltages on the address wires to the binary representation of seventeen and the data comes back.

So, yes, the hardware (i.e., the model of computation) does affect the running time of algorithms, as D.W. explains, but that's not what your array access example seems to be based on.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ To be fair, you skipped all the pieces in between "the memory controller sets the voltages on the address wires to the binary representation of seventeen" and "the data comes back". One of those pieces almost certainly is a binary search tree of the kind described by the OP; but it nonetheless executes in constant time because log n is approximately 64, for all n. $\endgroup$
    – Quuxplusone
    Commented Jun 22, 2018 at 2:01
  • $\begingroup$ @Quuxplusone What part of the memory uses binary search? The address lines directly select the memory cells. $\endgroup$
    – David Richerby
    Commented Jun 22, 2018 at 14:23
  • $\begingroup$ We're operating far far outside my area of expertise, but what I was trying to imply is that an address decoder will be implemented in terms of a tree of demuxers. (Assuming that we are directly hitting physical memory, ignoring any extra complication that comes with caching.) Again, all this extra complication adds only O(lg size-of-memory), i.e., negligible — but that's exactly the bit OP was asking about! $\endgroup$
    – Quuxplusone
    Commented Jun 22, 2018 at 18:10
2
$\begingroup$

No, the hardware doesn't affect the complexity of algorithms.

But, it does affect the choice of algorithm, and it can affect the usefulness of complexity analysis to a point where the analysis becomes pretty much meaningless (or merely of academic interest).

Finding the right drawer (as accessing an array element) uses the "open Nth element directly by index" algorithm, not the "search linearly" or "do binary search" algorithm. The algorithms are not changed, but the choice.

On the other hand side, complexity analysis itself, or rather its meaningfulness, is affected greatly by hardware.

Many algorithms that are stellar by their complexity analysis are poor performers or even useless in practice because the insignificant constant factor is not at all insignificant, but dominating.

Or, because assumptions that were once true (or mostly true) no longer hold. Such as, for example, every operation is mostly the same (only small constant differences that don't matter), or it doesn't make a difference which memory locations you access in which order. By complexity analysis, you may conclude that some algorithm is vastly superior because it only needs so and so many operations. In practice, you may find that each operation causes a guaranteed cache miss (or worse yet, page fault), which introduces a k that's so huge that it is no longer insignificant, but dominating everything.
If algorithm A takes 500 operations for processing a dataset of a given size and algorithm B takes only 5, but B causes 5 faults which burn twenty million cycles each, then despite what anaylsis or common sense may tell you, A is better.

This has lead to funny surprises such as e.g. in Cuckoo Hashing a few years ago. Which was vastly superior because [long list of benefits]. After the hype cooled, it turned out that it was vastly inferior because it guaranteed two cache misses (faults, for larger data sets) on every access.

Similar has happened to identifying and processing subsets of data. Often, the correct solution nowadays is: "just do it all", i.e. instead of figuring out what you need to proess and do that, process the complete dataset linearly even if you maybe only need half of it. Because, believe it or not, that's faster due to no branch mispredictions, no cache misses, no page faults.
Need to read the first 8kB and the last 3kB of a 3MB file? Well, read the complete file, and throw away what you don't want, because seeking in between will be ten times slower than just reading the complete thing.

Use a map because it has logarithmic complexity? Or a hash table, which has constant access time? Constant sounds awesome. Well, for anything with fewer than a thousand or so things (depending on hardware, data size, and access pattern), a linear search may be just as good or better. Surprise.

So, it's not the algorithms per se that are affected, but their usefulness, and choice.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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