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

Jerry Franz jfranz at freerun.com
Sun Dec 14 02:33:52 UTC 2008



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).

;)

-- 
Benjamin Franz



More information about the CentOS mailing list