What algorithms are proven to be the best?

Revision en2, by grimalk, 2015-10-30 01:27:32

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)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English grimalk 2015-10-30 01:27:32 507
en1 English grimalk 2015-10-29 16:25:24 207 Initial revision (published)