[CST-2] Kolmogorov complexity - cost of sorting

[Anthony Jones]

On Fri, May 31, 2002 at 05:15:11PM +0100, James Sutherland wrote:
> > well you need O(n) integers, but each one is O(log n) bits long....
> 
> Yes, but you are still sorting in O(n) time. The existence of a working
> O(n) algorithm does rather damage the chances of "proving" the hypothesis
> that you can't sort in less than O(n log n) time :-)

And exactly which algorithm can sort a list of ARBITARILY LONG integers in
O(n) time?

Ant

-- 
The obligatory bit about my email address:
This account will be closed on July 15th 2002.
Please use ant@cantab.net