[OT] stable algorithm with complexity O(n)

[Dan Upton]

On Sat, Dec 13, 2008 at 2:00 PM, David Hláčik <david at hlacik.eu> wrote:
>> 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.

This is only true for comparison-based sorts.

>
> There is n numbers from interval [1 , n^2]
> I should do measurement for :
> n = 500, 1000, 1500, 2000, ..., 4500, 5000
>
> O(n) means linear complexivity, so complexivity of algorithmus must be
> linear, which i have to prove.
>
>
>>
>> Who has given you that assignment - a professor? Or some friend who's
>> playing tricks on you?
>
> It is official assignment , by professor from Data Structures &
> Algorithms course.
>
> Thanks in advance!
>>
>> Diez
>> --
>> http://mail.python.org/mailman/listinfo/python-list
>>
> --
> http://mail.python.org/mailman/listinfo/python-list
>

Look at things like bucket sort and radix sort.  You can also do
tricky things like translating your problem domain by making a fixed
number of linear-time passes without affecting the asymptotic run
time.

(Hopefully that's helpful... don't want to give too much away on a
homework assignment, plus tricky algorithms have never been my strong
suit.)