[CentOS] [OT] stable algorithm with complexity O(n)
Jerry Franz
jfranz at freerun.com
Sat Dec 13 19:29:06 UTC 2008
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
More information about the CentOS
mailing list