I mean proven things like comparison sort can't have an asymptotic better than N * log(N). I haven't ever heard about other similar cases. Is there anyone who knows?
UPD: probably I did not describe the question properly enough, although zxqfl gave an answer I expected to get. I have meant that we have some sort of problem with strict restrictions, for example finding a minimal path from S to T in a graph with 1 ≤ w(e) ≤ 109 integer length of all edges and this is proven that this task can not be solved faster than in O(M * logN) or something like that. (Not exactly saying I know how to prove this, just giving an example)
