Subject: Re: quick newbie question
From: rpw3@rpw3.org (Rob Warnock)
Date: Tue, 04 Nov 2003 09:19:09 -0600
Newsgroups: comp.lang.lisp
Message-ID: <Q_icnccoXMbwXjqiXTWc-w@speakeasy.net>
Peter Seibel  <peter@javamonkey.com> wrote:
+---------------
| ...the constant factors might make a real difference. ObLisp: this is why
| sometimes alists could be more efficient than hash tables even though
| an alist lookup is O(N) while a hashtable lookup is usually O(log N):
| the constant factor on alists may well be much smaller.
+---------------

Actually, hash table lookup [with a well-designed hash and good
resizing of the hash table when necessary] can be as good as O(1).
Which is why people use hash tables...


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607