[CST-2] Kolmogorov complexity - cost of sorting

[Jonny Graham]

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'm confused...
jonny


Anthony Jones wrote:
> On Fri, May 31, 2002 at 05:15:11PM +0100, James Sutherland wrote:
> 
>>>well you need O(n) integers, but each one is O(log n) bits long....
>>
>>Yes, but you are still sorting in O(n) time. The existence of a working
>>O(n) algorithm does rather damage the chances of "proving" the hypothesis
>>that you can't sort in less than O(n log n) time :-)
> 
> 
> And exactly which algorithm can sort a list of ARBITARILY LONG integers in
> O(n) time?
> 
> Ant
> 


-- 
Jonny Graham
01223 565 373
07753 841 971

Selwyn College
Grange Road
Cambridge
CB3 9DQ

--My email account will cease to exist on 15/7/02--
--My new email address is jonnygraham@cantab.net --