Will the ultimate search for asymptotically fastest programs typically lead to fast or slow programs for arguments of practical size? Levin search, matrix multiplication and the algorithm Mp∗ seem to support the latter, but this might be due to our inability to do better.
Asymptotic complexity analysis is kind of broken, there's more of a tradeoff in using different algorithms than "\Theta(n) is better than \Theta(n \log n)" would indicate.
I wonder if a better framework exists, but that's probably several open research topics bundled in a single question.
I wonder if a better framework exists, but that's probably several open research topics bundled in a single question.