Sometimes vague or implicit assumptions can make it unclear whether an algorithm is asymptotically optimal. For example, a lower bound theorem might assume a particular abstract machine model, as in the case of comparison sorts, or a particular organization of memory. By violating these assumptions, a new algorithm could potentially asymptotically outperform the lower bound and the "asymptotically optimal" algorithms.
Sometimes vague or implicit assumptions can make it unclear whether an algorithm is asymptotically optimal. For example, a lower bound theorem might assume a particular abstract machine model, as in the case of comparison sorts, or a particular organization of memory. By violating these assumptions, a new algorithm could potentially asymptotically outperform the lower bound and the "asymptotically optimal" algorithms.
See also:
http://en.wikipedia.org/wiki/Abstract_machine
http://en.wikipedia.org/wiki/Random-access_stored-program_ma...
http://en.wikipedia.org/wiki/Cache-oblivious_model
etc.
As far as I know all asymptotic analysis has to be done using some abstract machine model.