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 21:09, Paolo Carlini wrote:
> Dhruv Matani wrote:
> 
> >> 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.
> 
> Please read again James postings. I think you don't get its simple, but
> very interesting point.
> 
> On any real-world machine the core memory is addressed by 64 bits, not more.
> Therefore computing log_2 of the biggest possible N leads to the small
> constant 64. You have to come up with a *very* fast linear algorithm (a very
> small K) to actually beat it!

Exactly that's the catch. You have mentioned about the k that's present
in O(N) algorithms, but what about the one present in the O(N.lg(N))
algorithms too? The k is everywhere. Just the OP hasn't mentioned it for
the O(Nlg(N)) algorithm. However I do agree with the fact that the lg(N)
factor would not exceed 64 and 32 on modern machines.


> And all of this raises another, even more general issue: the standard talks
> about Big-Oh notations which, ultimately, if I'm not wrong, are defined as
> _limits_ for N->+inf.
> 
> Therefore, for every possible _finite_ N, how we can possibly assess if
> an implementation is conforming without looking at the source code?
> 
> If a closed source vendor uses internally in the sort routines a very
> fine tuned shell sort algorithm which is actually better than quicksort
> for every real world size of the memory, how can we possibly counteract
> that?

By making sure that the export keyword is never implemented! ;-)





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