[CST-2] Kolmogorov complexity - cost of sorting

[David Singleton]

> but how does sorted version of the output turn out to be shorter than the
> inital version??????

It contains less information as it has fewer degrees of freedom?

i.e. it's confined to be monotonically increasing/decreasing  across it's
length.

log_2{n!} is the information content of a random sequence of length n
(it has n! possible orderings, so can communicate log_s{n!} bits of
information), the sorted version has 1 possible ordering, so conveys 0
bits)


-- 
David Singleton    _________________      St John's College, Cambridge
 C5 3rd Crt        +44(0)7980 641608   http://www.davidsingleton.co.uk/
!!my @cam.ac.uk address stops mid-June - use davidsingleton@cantab.net!!