From: William Morgan <wmorgan-ruby-talk@...>
Date: 2005-04-23T22:03:58+09:00
Subject: Re: Question: Time efficiency of Array <<

Excerpts from Peter Suk's mail of 23 Apr 2005 (EDT):
> >Excerpts from Ara.T.Howard@noaa.gov's mail of 22 Apr 2005 (EDT):
> >>yes that's true too.  i've done tests in the past comparing bdb,
> >>gperf, and other hashing type look ups against a bsearch and found
> >>them to be quite a bit slower.  on closer analysis it turned out that,
> >>although hashing is O(1), the call stack is so much deeper for each
> >>search as compared to a non-recursive bsearch that it predominates - i
> >>was suprised.
> >
> >Just goes to show that theoretic bounds on worst case performance are
> >sometimes just that....
> 
> It's actually that the upper bounds are too loose in the naive 
> analysis.  Amortized worst-case bounds on the doubling re-allocation 
> are O(n) for n insertions, or the same O(1) per insertion as hashing.  
> Then, it should become clear that the constant is bigger for hashing.

In this case he's talking about lookups and call stack depth.

-- 
William <wmorgan-ruby-talk@masanjin.net>