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.