[OT] stable algorithm with complexity O(n)

David Hláčik david at hlacik.eu
Sat Dec 13 20:00:07 CET 2008


> 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.

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
>



More information about the Python-list mailing list