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!