One of the main benefits of algorithm analysis, is that it offers asymptotic improvements to complexity as opposed to hardware, which offers only constant improvements. E.g switching to a super computer from a workstation might give a $\times 1,000,000$ increase in speed, but if that supercomputer is running a linear search on a sorted array, it will eventually be trumped by a desktop running a binary search for large enough problem sizes.

My question is this:

Are there any improvements in hardware(theoretical or practical) that could offer an asymptotic speedup over pre-existing hardware?

In this case pre-existing refers to at least 3rd generation computing technology. I'm not really interested in speedups over vacuum tubes.


Quantum computers, if they ever get built, will be asymptotically faster than existing computers in certain tasks. Limited quantum computers might already exist, though this is a contentious issue.

  • $\begingroup$ What's the speedup though? Polynomial or exponential? $\endgroup$ – Tobi Alafin Dec 31 '16 at 9:43
  • 1
    $\begingroup$ Depends on the task. Quantum computing is a wide topic, and I am not going to summarize it in this answer. There is plenty of information about quantum "supremacy" on the internet. $\endgroup$ – Yuval Filmus Dec 31 '16 at 9:44

Three-dimensional memory systems can improve the asymptotic complexity.

Suppose the CPU is in the center of the world, and the rest of the world is filled with memory cells. The CPU broadcasts a request to memory and waits a finite amount of time for a response.

If the memory is in the form of a 2-dimensional plane, then the CPU waiting $n$ nanoseconds can reach $\Theta(n^2)$ memory cells.

But if the memory is in the form of 3-dimensional space, then the CPU waiting the same $n$ nanoseconds can reach $\Theta(n^3)$ storage cells.

When a program needs to use $m$ memory cells for its execution, the 2D memory technology has a latency of $\Theta(\sqrt[2]{n})$ per operation, whereas the the 3D memory has a latency of $\Theta(\sqrt[3]{n})$.

  • $\begingroup$ This sounds amazing. Why hasn't this been done yet? $\endgroup$ – Tobi Alafin Jan 1 '17 at 7:44
  • $\begingroup$ @TobiAlafin Because the limiting factor is the number of gates, not the distance between CPU and memory. Actual memories are reached through a single bus; the number of cells that the CPU can access in time $n$ is $\theta(n)$, limited by the bandwidth of the bus, the address decoder and the refresh mechanism. $\endgroup$ – Gilles 'SO- stop being evil' Jan 1 '17 at 21:17
  • $\begingroup$ @Gilles I think a CPU can access more than $n$ cells in $n$ time. I think it can access $n^2$ cells because a request can spread out in 2D space. $\endgroup$ – Nayuki Jan 1 '17 at 21:28
  • $\begingroup$ @TobiAlafin I think it's because semiconductor manufacturing revolves around single chips with a small number of logic layers. Only slowly are we starting to see more vertical stacking with technologies such as 3D NAND flash memories. $\endgroup$ – Nayuki Jan 1 '17 at 21:28
  • 1
    $\begingroup$ @Raphael: I think this answer persuasively argues that some new kinds of physical computing devices can be modelled well by different (fine-grained) model of computational complexity. (A similar example would be going from a tape drives (modelled well by $O(n)$ memory access times) to SSDs (modelled well by $(\log n)$ access times, or if you squint, maybe $O(1)$).) $\endgroup$ – j_random_hacker Jan 11 '17 at 15:21

As long as you stay in the realm of real, classical computation (i.e. a finite, discrete symbol set; finite control; finite memory): no. Real machines do not have any asymptotic nature so you can not speed them up asymptotically, either.

If you allow different theoretical computation models, the answer is trivially yes: different models imply different complexities for the same problem. Just compare TMs with RAMs.


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.