[CentOS] [OT] stable algorithm with complexity O(n)

Nicolas Thierry-Mieg Nicolas.Thierry-Mieg at imag.fr
Sun Dec 14 16:40:56 UTC 2008

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?

More information about the CentOS mailing list