Re: No quadratic allocators

Issac Goldstand <[email protected]> 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