[OT] stable algorithm with complexity O(n)
MRAB
google at mrabarnett.plus.com
Sat Dec 13 14:20:54 EST 2008
Diez B. Roggisch wrote:
> David Hláčik schrieb:
>> Hi guys,
>>
>> i am really sorry for making offtopic, hope you will not kill me, but
>> this is for me life important problem which needs to be solved within
>> next 12 hours..
>>
>> I have to create stable algorithm for sorting n numbers from interval
>> [1,n^2] with time complexity O(n) .
>>
>> Can someone please give me a hint. Would be very very thankful!
>
> Unless I grossly miss out on something in computer science 101, the
> lower bound for sorting is O(n * log_2 n). Which makes your task
> impossible, unless there is something to be assumed about the
> distribution of numbers in your sequence.
>
> Who has given you that assignment - a professor? Or some friend who's
> playing tricks on you?
>
I'm assuming that the numbers are integers. I can think of an O(n)
algorithm for this particular problem provided that n isn't huge, but if
it's your assignment then it's up to you to discover it.
More information about the Python-list
mailing list