On Sat, Dec 13, 2008 at 2:00 PM, David Hláčik <da...@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.) -- http://mail.python.org/mailman/listinfo/python-list