How Fast do Algorithms Improve?

Algorithms are a crucial aspect of computing. However, there is little concrete evidence about how fast algorithms improve, and current information is mostly anecdotal and based on small case studies. 

Yash Sherry and Neil Thompson have conducted a comprehensive study by analyzing data from 57 textbooks and over 1,137 research papers, which presents the first systematic view of algorithm progress ever assembled. Their findings show that there is a wide range of variation in algorithm improvement rates. Approximately 50% of all algorithm families do not improve significantly, while 13% experience transformative progress.

This progress can radically change how and where they can be used.   Overall, the study found that for moderate-sized problems, 30% to 45% of algorithmic families experienced improvements that were comparable to or greater than those experienced by users from Moore’s Law and other hardware advances.

‍
Access the article