On Mon, 10 Feb 2014 10:20:33 +0000, Sturla Molden wrote: > Wesley <nisp...@gmail.com> wrote: >> [Wesley] This is not homework:-) >> And actually I am new to algorithm, so you guys can feel free to say >> anything you want > > In general, we cannot sort a sequence in O(n) time. O(n log n) is the > lower bound on the complexity.
Firstly, you're talking about average complexity, not best-case complexity. The base-case can be O(N) for a sequence which is already sorted. Worst case can be much greater, e.g. O(N**2) for Quicksort, or unbounded for Bogosort. (That is, Bogosort is not guaranteed to sort a sequence even after infinite time!) Secondly, O(N*log N) applies to *comparison sorts*. Non-comparison sorts such as radix-, counting- and bucket-sort have average case complexity of O(N). See, for example: http://algorithmstwo.soc.srcf.net/resources/asides/noncomparison/ http://en.wikipedia.org/wiki/Bead_sort http://en.wikipedia.org/wiki/Radix_sort http://en.wikipedia.org/wiki/Spaghetti_sort etc. -- Steven -- https://mail.python.org/mailman/listinfo/python-list
