wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Sort
        
(Message started by: mad on Mar 7^th, 2008, 10:45pm)

Title: Sort
Post by mad on Mar 7^th, 2008, 10:45pm

Show how to sort n integers in the range 0 to n^2-1 in O(n) time.
I think convert the number into base2 and apply radix sort. Is this correct?

Title: Re: Sort
Post by towr on Mar 8^th, 2008, 2:25am

What sort of computer do you have that doesn't already store numbers in binary? ::)

I'm not sure whether the preferred answer is radix sort, but it works.

Title: Re: Sort
Post by m_aakash on Mar 8^th, 2008, 1:39pm

if you use radix sort with radix 2 then it will take
O(n log(n^2-1)) time in worst case. this is no longer a linear solution.