Christopher Wright wrote:
bearophile wrote:
Andrei Alexandrescu:
Your handwaving ain't much better than my memory. Hey, either
somebody goes through the math over here or we can give up on the
whole thing and use O(n) storage for the blessed thing.<
We can implement both, and we can look what's better in practical
situations.
Agreed. Worst-case quadratic can perform much better in many
circumstances, and the proposed algorithm is tunable.
I think if we want to look like professionals we're not going to do
that. History of computing is full of embarrassing quadratic algorithms
failing miserably when advances in storage capacity or simply data set
growth within the original program showed their pernicious tendencies. I
have authored such a program when I was a student :o).
Andrei
