|Just another Perl shrine|
Re: Re: A short meditation about hash search performanceby Anonymous Monk
|on Nov 16, 2003 at 05:19 UTC||Need Help??|
Perhaps I need to re-review the analysis of CLR-1990*, because they clearly state on page 223:
The worst-case running time for insertion is O(1). For searching, the worst-case running time is proportional to the length of the list: we shall analyze this more closely below. Deletion of an element x can be accomplished in O(1) time if the lists are doubly linked.
Note, I wasn't referring to perl's hashes in particular, just hashes in general.
* Cormen, Leiserson, Rivest 1990: Introduction to Algorithms. MIT Press, Cambridge Massachusetts.