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?