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 + n1 + n2 + ... + 1, where n
> is the number of packets received...
But n + n1 + n2 + ... + 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) + (n1 + 2) + (n2 + 3) + ... + (n/2+1 + n/2)
 
+ n/2 pairs +

Joe Schaefer
