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