On Thu, 3 May 2001, John J. Lee wrote:

> 
>  [I wrote]
>  > There are O(N) sorting algorithms??  I thought that was restricted to
>  > quantum computation.
>  [...]
> 
>  Actually, there is no quantum algorithm that works better than O(N ln N)
>  either.  There is a *search* that is better than the classical limit.

Not yet, anyway.It's provable that you can't do comparison based sorting
in less  time than O(N ln N), unless you can make  N log N comparisons take less than N
Log N time (IE less than O(1) per comparison).
You might actually be able to pull off the < O(1) per comparison on a
quantum computer by finding some way to evaluate more than one comparison at a time, and hav
e it take
the same time as just one (You can already do this type of thing if you
have multiple CPU's.)
--Dan


-- 
http://mail.python.org/mailman/listinfo/python-list