Balanced trees

[Steven D'Aprano]

On Sun, 09 Mar 2014 23:32:54 +0200, Marko Rauhamaa wrote:

> Dan Stromberg <drsalists at gmail.com>:
> 
>> This is not just a detail: O(1) tends to be beat O(logn) pretty easily
>> for large n.
> 
> There is no O(1) hash table.

Of course there are.

While it is true that hash tables *in general* are not *always* O(1), the 
claim that hash tables are O(1) is *less wrong* than your claim that 
there is "no O(1) hash table".

Proof: I create a hash table that accepts unsigned bytes as keys, where 
the hash is the value of the byte. So byte 0x42 hashes to 0x42, or 
decimal 66. I give the hash table 256 slots, numbered from 0 to 255. 
Every hash takes constant time, there are no collisions at all, lookups, 
insertions and deletions all take constant time regardless of how full 
the table is. The best, worst and average cases are not just O(1) but 
also Ω(1).

Since I have proven that there is *at least one* hash table that is O(1) 
for best, worst and average case, your claim there are no such hash 
tables is completely wrong, and certainly more wrong than the claim that 
Python dicts are O(1) (which is only a little bit wrong, but typically 
right).

See also "The Relativity Of Wrong":

http://chem.tufts.edu/answersinscience/relativityofwrong.htm




-- 
Steven D'Aprano
http://import-that.dreamwidth.org/