[OT] stable algorithm with complexity O(n)
upton at virginia.edu
Sat Dec 13 20:08:19 CET 2008
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!
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
(Hopefully that's helpful... don't want to give too much away on a
homework assignment, plus tricky algorithms have never been my strong
More information about the Python-list