[CST-2] Kolmogorov complexity - cost of sorting

[Anthony Jones]

On Fri, May 31, 2002 at 05:32:37PM +0100, Jonny Graham wrote:
> But this O(n) algorithm isn't 'sorting' it's just rearranging by a fixed 
>  list of swaps. If instead of 'cheating' with a list of swaps to do to 
> sort I 'cheated' by passing it a list of the same numbers sorted, I 
> could 'sort' in O(1) time by just returning the sorted version;-)

I really don't know what you're getting at now I'm afraid! :)

Ant

-- 
The obligatory bit about my email address:
This account will be closed on July 15th 2002.
Please use ant@cantab.net