[CST-2] Kolmogorov complexity - cost of sorting

[John Wyllie]

I asked ACN about this earlier, this is what he said.

John


On Tue, 28 May 2002, John Wyllie wrote:

> Dr Norman -
> 
> I have some scribbled notes I took during one of your Advanced Algorithms
> examples class about "The cost of sorting"
> 
> What I have scribbled down is as follows:
> 
> ------
> sort n items (initially in RANDOM (ie. not compressible) order)
> there are n! permutations.
> must do binary comparisons.
> so cost -> log(n!) which roughly equals n.log(n)
> suppose we could sort in LESS THAN n.log(n)-C comparisons...
> CONTRADICTION!
> ------
Look at the sorting algorithm. Replace any test "if (a<b)" with 
"if(next-bit-of-input()==1)" and you get a program that reads a stream of
bits and on that basis permutes an array of n values. Thus the stream of
input bits is a representation of that permutation. If the method could
sort ANY input it must be able to generate ANY permutation. Specifically
it can generate incompressible permutations (and most perms are
incompressible). Thus the bit-stream I just mentioned must be as long as
the natural description of such a permutation, ie log(n!).

You will find that a web search on Kolmogorof complexity picks up a bunch
of pages and sets of course-notes etc. The main serious books on it are
too long and detailed for you to want to look at them this close to the
exam!
                 Arthur Norman