[CST-2] Kolmogorov complexity - cost of sorting

[Alan Lawrence]

well you need O(n) integers, but each one is O(log n) bits long....

--Alan

On Friday, May 31, 2002, at 04:42  pm, James Sutherland wrote:

> 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.
>
>
>
> _______________________________________________
> CST-2 mailing list
> CST-2@srcf.ucam.org
> http://www.srcf.ucam.org/mailman/listinfo/cst-2