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
