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 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. So when worrying about the worst case, doing lots of insertions, deletions, ordering and the like, balanced trees are better, although they are not implemented by the guile-core? Klaus Schilling