[CST-2] Kolmogorov complexity - cost of sorting

[James Sutherland]

On Fri, 31 May 2002, Jonny Graham wrote:

> Yes. You're right. I wrote a small program to wipe my HDD and, yes, I
> can't get it back ;-)
> The inverse program *and* the steps [ which are <<nlog(n) ] that were
> taken in sorting would allow this to work. It's this that would be
> shorted than nlog(n) because the #steps in sorting is <<nlog(n) and the
> size of this program is negligent.
>
> Hope that now makes more sense and is slightly less impossible.

It now makes sense, but you can also reverse the sorting with O(n) (in
fact, precisely n) integers: just record the original position of each
value in the output. To reverse, copy each value back to its original
position: O(n) "unsorting" using O(n) space and time.


James.