Speedup from algorithmic advances vs. hardware I recall seeing a study or article a while ago claiming that most of the speedup seen in computer programs over the last several decades is from better algorithms rather than faster hardware. Does anyone know the study or article?
this is an unintentionally complex question. this idea that software gains have outpaced hardware gains is apparently rooted in a real govt report but (as your question indicates) possibly approaching minor urban legend status due to being misunderstood or misinterpreted. the summary/sound-bite headlines do not really match the actual point being made in the report.

see [1] or [2] which states


  A report by an independent group of science and technology advisers to the White House, published last December, cited research showing that performance gains in doing computing tasks that result from improvements in software algorithms often far outpace the gains attributable to faster processors.
  ...
  But the White House advisory report cited research, including a study of progress over a 15-year span on a benchmark production-planning task. Over that time, the speed of completing the calculations improved by a factor of 43 million. Of the total, a factor of roughly 1,000 was attributable to faster processor speeds, according to the research by Martin Grotschel, a German scientist and mathematician. Yet a factor of 43,000 was due to improvements in the efficiency of software algorithms.


but the issue of software vs hardware is very far from this one dimensional simplification, much more complex, and Lohrs blog has it more accurate— software and hardware form a sort of yin-yang symbiotic fusion and both have advanced very significantly, even staggeringly over the decades.

caveat/fine print: one cannot take individual gains in particular software algorithms, which in some cases have been very substantial, and generalize that across all algorithms.

the actual quote from the report is on page 71:


  Even more remarkable – and even less widely understood – is that in many areas,
  performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed. The algorithms that we use today for speech recognition, for natural language translation, for chess playing, for logistics planning, have evolved remarkably in the past decade. It’s difficult to quantify the improvement, though, because it is as much in the realm of quality as of execution time.


so this government report is highly researched and polished, the basic claim of massive gains due to theoretical software advances in some areas is correct, and is promoting (theoretical/algorithmic) research partly on that basis.

however there are several other new/recent fundamental/massive phenomena/trends/shifts in recent years or what Intels Grove calls "inflection points" that are occuring in hardware vs software design. aka "gamechangers":


the rise of "Exascale" supercomputing may not be as readily achieved as "Petascale" due to hardware scaling constraints
clock speeds, a main drive of prior speed gains, have plateaued (partly due to heat/cooling constraints)
hardware is undergoing a massive shift toward less compute intensive, more energy efficient devices eg mobile, datacenters/virtualization/cloud etc
improving parallelism in software and hardware (eg "multicore") is therefore becoming more critical for performance improvements (where theory has a lot to say about how to parallelize algorithms)




[1] skeptic.se, does progress in algorithms beat progress in hardware

[2] Software progress beats Moores law NYT blog by Lohr

[3] REPORT TO THE PRESIDENT
AND CONGRESS
DESIGNING A DIGITAL FUTURE:
FEDERALLY FUNDED RESEARCH
AND DEVELOPMENT IN
NETWORKING AND INFORMATION
TECHNOLOGY Dec 2010