[CentOS] [OT] stable algorithm with complexity O(n)
Jerry Franz
jfranz at freerun.com
Sun Dec 14 17:17:16 UTC 2008
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.
--
Benjamin Franz
More information about the CentOS
mailing list