httpd-apreq-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Joe Schaefer <joe+gm...@sunstarsys.com>
Subject Re: No quadratic allocators
Date Tue, 08 May 2007 14:26:14 GMT
Issac Goldstand <margol@beamartyr.net> writes:

> Maybe I'm missing something in the math behind this, but the current
> code [I'll mention now that I don't have the current source at hand as
> of the time of writing this, so maybe I'm missing some context]
> shouldn't be allocating n^2, but rather n + n-1 + n-2 + ... + 1, where n
> is the number of packets received...

But n + n-1 + n-2 + ... + 1 sums to n * (n+1) / 2 (and thus O(n^2)),
which can be seen by grouping first and last terms together:

(n + 1) + (n-1 + 2) + (n-2 + 3) + ... + (n/2+1 + n/2)
  |                                        |
  +------------ n/2 pairs -----------------+

-- 
Joe Schaefer


Mime
View raw message