[CST-2] Kolmogorov complexity - cost of sorting

[James Sutherland]

On Fri, 31 May 2002, Tom Puverle wrote:

> > Nope. It's **NOT** a fixed list of anything. It runs through the input
> > some constant number of times, building progressively "more sorted" and
> > smaller subsets of the input, until they are all fully sorted. (The
> > constant number of times is determined by the size of input;
>
> That doesn't sound like a constant to me then...
> O( C(N) * N ) is NOT in general equal to O( N )

It is *NOT* C(n): the size of integer (or other value) is independent of
N. e.g. sorting ASCII strings: double the number of strings, and this
algorithm takes twice as many operations. The strings do not get longer,
hence the constant remains constant.

> When you need to compare the elements on a pair by pair
> basis you will find that C(N) is lg N.

Except I don't know of any data types for which that is the case.

> I believe what you are describing as your sorting algorithm
> is radix/bucket sort, which will run in O( N ), but that's
> only true because they make assumptions about the input.

The assumption is that you can compare values using a subset of the bits
in the representation. What well-ordered sets of values do not have this
property, if any?


James.