This is the mail archive of the guile@cygnus.com mailing list for the guile project.
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
Keith Wright <kwright@tiac.net> writes: > > From: Klaus Schilling <Klaus.Schilling@home.ivm.de> > > Harvey J. Stein writes: > > > > > > Nope. Resizing hashtables are still O(1) for insertions. See the > > > previous discussions & 3 independently posted analyses. God, I wish > > > this list had a shorter turn-around time. > > > > Even in the worst case, when all entries drop into the same bucket? > > Obviously not. Any claim of O(1) performance for hashtable insertion, > deletion, or re-size is average case assuming a random hash. If you > are talking about hash-tables, you are not talking worst-case. This is exactly what makes comparison of hash tables & balanced trees difficult. The analyses of hash tables quoted here aren't even average case (in a rigorous probabalistic sense), they've been, in some sense, good case analyses in that they assume bounded bucket sizes. The worst case is pretty bad. On the other hand, balanced trees are O(log(n)) in the worst case as well as on average. -- Harvey J. Stein BFM Financial Research hjstein@bfr.co.il