[OT] stable algorithm with complexity O(n)
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 &
Thanks in advance!
More information about the Python-list