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

Paolo Carlini pcarlini@suse.de
Wed Feb 4 15:37:00 GMT 2004


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!

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?

Hummm.

Paolo.



More information about the Libstdc++ mailing list