References

TL;DR

  • about half of algorithm families had YoY improvements that were equal to or larger than the much-touted gains from Moore’s Law
  • The single biggest change that the authors observed came when an algorithm family transitioned from exponential to polynomial complexity.
  • Hardware improvement from Moore’s Law happens smoothly over time, and for algorithms the gains come in steps that are usually large but infrequent.