This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: N*log(N) doesn't exist (Re: [RFC] Vector (string?) growth...)
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.