From: Peter Suk <peter.kwangjun.suk@...>
Date: 2005-04-23T13:21:41+09:00
Subject: Re: Question: Time efficiency of Array <<

On Apr 22, 2005, at 11:02 PM, William Morgan wrote:

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

--Peter

--
There's neither heaven nor hell, save what we grant ourselves.
There's neither fairness nor justice, save what we grant each other.