Sort one sequence by O(n) in time and O(1) in space

Steven D'Aprano steve at
Tue Feb 11 06:20:28 CET 2014

On Mon, 10 Feb 2014 10:20:33 +0000, Sturla Molden wrote:

> Wesley <nispray at> 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:



More information about the Python-list mailing list