On Wed, 25 Feb 2004, Poor, Edmund W wrote:
As a programmer with well over a quarter century of
experience, I
applaud this effort by Nick to identify and slay the "dragon" of
N-squared performance.
When a process on a file takes time proportion to the file size, we call
that N. When time is proportion to log N, we call that log N performance
(quicksort, which uses a partition scheme and then sorts the partitions,
has log N performance).
A process whose elapsed time grows in proportion to the SQUARE of the
file size is out of control! It's called an N-squared or N^2 process,
and is to be avoided like the plague. Insertion sort and Bubble sort are
examples, and have long been shunned for all but small numbers of items.
I should point out that average article size isn't growing, at least not in any
significant sense.
So on the larger scale, we have N performance.
(I'm not taking into account the fact that average size might conceal much
larger differences in performance because of the N^2 parser. But it's still
only the number of articles that's "out of control" here.)
-- Daniel