stable algorithm with complexity O(n)

denisbz at t-online.de denisbz at t-online.de
Mon Dec 22 18:29:36 CET 2008


On Dec 15, 10:00 pm, "cmdrrickhun... at yaho.com"
<conrad.am... at gmail.com> wrote:
> It can be proven that you cannot sort an arbitrarily large set of
> numbers, given no extra information, faster than O(n log n).

Cormen Leiserson and Rivest, "Algorithms", have a short clear chapter
on
"Sorting in linear time":
    " ... counting sort, radix sort and bucket sort ... use operations
other than comparisons.
    Consequently, the Omega( n lg n ) lower bound does not apply to
them."

Some of the book is in books.google.com; enjoy



More information about the Python-list mailing list