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

Sun Dec 14 15:24:33 UTC 2008
Marko Vojinovic <vvmarko at panet.co.yu>

On Sunday 14 December 2008 03:33, 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).
>
> ;)

Oh, you mean because the upper bound is n^2, right? Sure, of course, this 
particular case is O(n^2). Your proposal in your other post with the square 
roots would probably improve that in this case.

However, I was just giving the OP a hint in the general direction of a typical 
O(n) algorithm, didn't have an intention to provide a full working solution 
for his specific case. It's his homework, not mine. ;-) 

:-)
Marko