[DennisP]

No, they really do mean that on the same hardware, solving the same problems, we have algorithms that will solve those problems 43,000 times faster compared to fifteen years ago...at least for the problems they looked at. And that progress is continuing.

The assumption here is that at any given time, you're reading the latest published papers and implementing the best known algorithms, in a field that uses complicated algorithms on big problems.

It's not just because of faster chips that Google has a self-driving car now.

(As for sorting, it's been proven that the best you can do is O(n log n), and John von Neumann achieved that with mergesort in 1945.)

[Retric]

With a large enough data set O(n^2) vs O(n^1.99999) be 43,000 times faster or 43,000,000 times faster. Which is one of the reasons that metric is next to meaningless. Looking back you can find plenty of great speedups but as I said it's in no way steady progress across all fields.

PS: Also Radix sorting is O(n) operation under conditions where mergesort is O (n log n). (AKA in practice merge sorting distinct strings is 0 (n * (log n) * (log n) as you need to look at an ever increasing number of symbols, or if your strings have a fixed max length or if your theoretical computer can compare infinitely long strings in a single step then Radix sorting is also O(n).)

[DennisP]

I should have specified "for sorting algorithms that depend on comparing elements to each other."

You're right that it's difficult to measure algorithm progress, but using problem sizes that you're interested in running in practice is probably a decent heuristic. "I wanted to run this problem but it would have taken 80 years. But then I caught up on recent published algorithms and look, I can do it in an hour on the same machine."

I don't think I claimed the progress was steady. Then again, Moore's Law might get more jumpy as silicon wafers reach their limits, and we transition to memristors, spin devices, or whatever else they come up with.