Running time depends on the model of computation. For example, the problem "Given strings $s$ and $t$, are they identical?" takes quadratic time on a one-tape Turing machine. So you can give a more reasonable model of computation... and the next person to come along will explain how it is much too strong, etc.
Hmmm. Perhaps your question might be rephrased in terms of using some other resource (which in turn requires at least a set amount of time). So perhaps invent a decision problem around sorting, and appeal to the $n\ln(n)$ lower bound...