Running time depends on the model of computation. Eg the problem "Given (m, n, p) does m + n = p?" takes at least 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 nlog(n) lower bound...