[CentOS] [OT] stable algorithm with complexity O(n)
Nicolas Thierry-Mieg
Nicolas.Thierry-Mieg at imag.fr
Sun Dec 14 18:49:55 UTC 2008
Jerry Franz wrote:
>
> 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.
>
oh, I see
thanks for explaining!
More information about the CentOS
mailing list