N*log(N) doesn't exist (Re: [RFC] Vector (string?) growth...)

[Paolo Carlini <pcarlini at suse dot de>]

Matt Austern wrote:

> I don't think that is a good suggestion.  In fact, I don't think it is 
> standard
> conforming.
>
> It's easy to prove that if you have a constant growth factor, i.e. if 
> you're
> using exponential growth, then adding one element is amortized
> constant time, as required by the standard.  That is, the number of
> copies you perform when you add N elements at a time is O(N).

I want to add something about the Big-O notation vs real in-memory 
algorithms...

Perhaps I'm naive but I have really enjoyed a simple observation put 
forward by
James Kanze in that original thread: for a real computer and a real in 
memory
algorithm N*log(N) can be bounded by N*32 or N*64 at most, that is N 
multiplied
by a constant quite small! A linear algorithm :-O

Then, he also offered interesting real world examples about sorting 
algorithms,
for instance.

This is only to briefly remind that, after the basic conformance 
requirements,
there is *much* to do for real world in memory vectors and strings and 
so on...

Paolo.