https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=954...
It loses any feeling of objectivity, but it'd be interesting to broaden the question to approximate or specialized solutions, or things that make larger problems practical to solve without improving big-O. For some examples:
- probabilistic sketches have been very successful at approximately answering questions that took a lot more work to answer exactly
- adapting algorithms to hardware like GPUs doesn't reduce how many operations are done, but can make the operations cheaper/faster for the right problem
- similarly, a good parallel or distributed approach to a problem doesn't change the big-O, but is often what allows scaling up to big n in practice
- the B-tree (1970) did not improve on the big-O of the AVL tree (1962), but it made databases as we know them a lot more practical
- LSM trees and compressed columnar storage also don't improve big-O, but provide big benefits for write-heavy and scan-heavy workloads
Generally that pushes me more towards "hardware isn't responsible for all the advancements". Also, there's a fun conversation (happening out there, I assume) about how to value the sort of work that's more pragmatic than improving on a complexity bound but also more fundamental than just tuning some asm or C.
I'd bet lazily slapping caches on things has saved more total time than all other computer optimizations combined.
For compilers, "Proebsting's law" suggests the total gain from all compiler research to date has been ~3%/year or >3.3x total: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29...