Speedup
The nonexistence of an asymptotically optimal algorithm is called speedup. Blum's speedup theorem shows that there exist artificially constructed problems with speedup. However, it is an open problem whether many of the most well-known algorithms today are asymptotically optimal or not. For example, there is an O(nα(n)) algorithm for finding minimum spanning trees, where α(n) is the very slowly growing inverse of the Ackermann function, but the best known lower bound is the trivial Ω(n). Whether this algorithm is asymptotically optimal is unknown, and would be likely to be hailed as a significant result if it were resolved either way. Coppersmith and Winograd (1982) proved that matrix multiplication has a weak form of speed-up among a restricted class of algorithms (Strassen-type bilinear identities with lambda-computation).
Read more about this topic: Asymptotically Optimal Algorithm