Re: [OT] stable algorithm with complexity O(n)

[Jerry Franz <jfranz@xxxxxxxxxxx>]

David Hláčik wrote:
> Well, something with linear complexity O(n) which i have to prove,
> 
> Merge sort, Insertion sort or selection sort does not have O(n) complexity.
> 
> I believe that something like RadixSort, CountingSort, BucketSort
> altought i am not sure

I'm not especially inclined to do someone's homework for them. But since 
you asked for a hint...My mathematical intuition suggests starting by 
mapping the data into an array of n buckets where each bucket is 
determined by the integer part of the square root of each number in the 
dataset.

--
Benjamin Franz
_______________________________________________
CentOS mailing list
CentOS@xxxxxxxxxx
http://lists.centos.org/mailman/listinfo/centos