# [OT] stable algorithm with complexity O(n)

Lie Ryan lie.1296 at gmail.com
Sun Dec 14 22:42:33 CET 2008

```On Sat, 13 Dec 2008 19:17:41 +0000, Duncan Booth wrote:

> "Diez B. Roggisch" <deets at nospam.web.de> 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 think you must have fallen asleep during CS101. The lower bound for
> sorting where you make a two way branch at each step is O(n * log_2 n),
> but if you can choose between k possible orderings in a single
> comparison you can get O(n * log_k n).
>
> To beat n * log_2 n just use a bucket sort: for numbers with a known
> maximum you can sort them digit by digit for O(n log_k n), and if you
> don't restrict yourself to decimal then k can be as large as you want,
> so for the problem in question I think you can set k=n and (log_n n)==1
> so you get O(n)
>

I'm sure someday, there will be a student who comes to class late and
sees this on the board: "Design a comparison sorting algorithm that has
better than O(n * log n) lower bound complexity." The unsuspecting
student copied it, thinking it's a homework. He crunched to the problem,
going to various meditations and yoga classes before finding a way that
works just before deadline, handing out the work a bit late. Six weeks
later, his professor called and said: "You know what you just did? You've
just found a problem that was supposed to be an example of unsolvable
problem."

It has happened before, why not again?
http://www.snopes.com/college/homework/unsolvable.asp

```