O(n^2) is bad - can it be fixed?

[Carlos Ribeiro]

Just an idea - isn't a paged array better suited for this kind of stuff? It 
would scale pretty well. I do remember that Unix has a similar structure 
for disk block allocation. For small lists a single lookup is needed; for 
large ones a few extra lookups could be compensated by avoiding the 
realloc() performance hit.

Of course, we assume that the problem is related to the list structure 
itself. The list elements are still subject to their own allocation 
policies. Also bear in mind that operations such as insertion and deletion 
could take a potentially bigger performance hit. However, I feel that such 
operations should not be an issue anyway, at least for large arrays; the 
only way we can remotely hope of performing them efficiently (for large 
lists)  is using  linked lists, or other more complex data structures.

Just my $.02 worth.


Carlos Ribeiro