Thank you guys for help and support! My homework is done and waiting for grading. Here it comes - bucket sort with time complexity O(n) == linear complexity #! /usr/bin/python def sort(numbers): "sort n positive integers in O(n) provided that they are all from interval [1, n^2]" N = len(numbers) # get size of test numbers buckets_mod = [[] for i in xrange(N)] buckets_sorted = [[] for i in xrange(N+1)] # group numbers to buckets (list of numbers) with common modulus for n in numbers: buckets_mod[n % N].append(n) print "buckets_mod: %s" % buckets_mod # check numbers in buckets for l in buckets_mod: for n in l: # place number into bucket number grouped by result of division buckets_sorted[n / N].append(n) print "buckets_sorted: %s" % buckets_sorted # search through sorted buckets and return list of sorted numbers return [n for l in buckets_sorted for n in l] Regards, David On Sun, Dec 14, 2008 at 7:49 PM, Nicolas Thierry-Mieg <Nicolas.Thierry-Mieg at imag.fr> wrote: > > > Jerry Franz wrote: >> >> Nicolas Thierry-Mieg wrote: >>> Jerry Franz wrote: >>>> Marko Vojinovic wrote: >>>> [...] >>>>> Basically, count the number of appearances of every number in your set. If you >>>>> have a set a priori bounded from above and below --- which you do, >>>>> [1, n^2] --- you first allocate an array of integers of length n^2. >>>> By definition, your proposed algorithm is O(n^2), not O(n). >>> No it isn't, it's O(n) in time. >>> O(n^2) in memory but that wasn't the question, right? >> >> Look closer at it. >> >> "[...] >> you first allocate an array of integers of length n^2. Set all >> elements to zero," >> [...] >> go through the whole set from 1 to n^2, and if the value of k-th element >> is nonzero, print number k appropriate number of times. >> [...]" >> >> O(n^2) operations are required. It is O(n^2) both in time and memory as >> described. >> > > oh, I see > thanks for explaining! > _______________________________________________ > CentOS mailing list > CentOS at centos.org > http://lists.centos.org/mailman/listinfo/centos >