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

[Dhruv Matani <dhruvbird at gmx dot net>]

On Wed, 2004-02-04 at 03:58, Paolo Carlini wrote:
> 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

I don't think so, because by the definition of the O notation, we have
already stripped away the constants and arrived at the O(Nlg(N)) result.
So, basically what this is telling us is that the actual number of
operations that are performed are directly proportional to Nlg(N) and in
reality the number of operations will be == K.Nlg(N), where K is a
natural number. So, K may be 10, 200, 300, 5, 60000, etc... Now, we can
not afford to replace lg(N) by the actual upper bound that the machine
will probably have (32 & 64 for 32 and 64-bit machines). Also, most of
the algorithms that have the above kind of complexity are
divide-and-conquor kind of algorithms, so, at every stage for each stage
in the lg(N) stages, N will be different. However, the original N in
lg(N) is the total number of inputs and for each of those passes over
the data, the linear factor N that makes Nlg(n) keeps getting smaller as
the algorithm proceeds. Hence the name Upper Bound for the Big-Oh
notation.


> 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...

I would say that the complexity guarantees hold in the real world only
when one knows what he/she is doing. If you just blindly believe that a
O(N) algorithm will do better in any case than a O(Nlg(N)) algorithm,
then you are probably mistaken, because O notation does not say anything
about:

1. Memory usage.
2. Cache locality / thrashing.
3. Disk usage / access time, etc...

And all the other factors that make up an algorithm. It is a purely
theoretical quantity and must be used with care. Of course, there are
others (I think all of you!) on the list that are much more experienced
that I am, and I don't know whether they will fully agree with me
bacause I may be wrong here since I have not programmed much.




-- 
	-Dhruv Matani.
http://www.geocities.com/dhruvbird/