[EMAIL PROTECTED] wrote: > I would like appreciate if somebody do a comparison with his best > algorithm with method mentioned in DOCTOR DOBBS and invented by A. > Andersson. They claims O(NloglogN) time. How does it behave in real > world?
I don't have access to DDJ, but if this is a comparison sort, the time bound must be wrong. There is a simple information theoretic argument that comparison sorting is Omega(n log n). It goes roughly like this: Sorting is equivalent to discovering the permutation of the data that places it in sorted order. There are n! permutations of a list of n items. A single comparison of the form A(i) < A(j) can eliminate at most half the possible permutations from consideration. If you don't see this, then think about an "adversary" who gets to choose a permutation that you are trying to "discover." If you claim you can eliminate more tha half the permutations with one comparison, the adversary can choose a permutation that defeats your claim. That means you need at least ceiling(log_2(n!)) to reduce the set of possibilities to 1, and log_2(n!) = O(n log n). --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
