[CST-2] Kolmogorov complexity - cost of sorting

[James Sutherland]

On Fri, 31 May 2002, Anthony Jones wrote:

> 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?

The "n" refers to the number of integers, not their size/value; making the
integers larger increases only the constant of proportionality, not the
value of n.


James.