- From: Maciej Stachowiak <mjs@apple.com>
- Date: Tue, 16 Jun 2009 12:37:57 -0700
On Jun 15, 2009, at 4:19 PM, Kristof Zelechovski wrote: > The complexity of using a set implemented as hash table is quadratic > in the > number of elements because of hash collisions. Removing duplicates from a list of length N using an auxiliary set is average-case O(N) because insertion and membership testing in a hash- implemented set is amortized average-case O(1). With a good hash function, the worst case does not usually need to be considered, because it is exceedingly unlikely to occur for a large data set by chance, and cannot feasibly be constructed by an attacker. Regards, Maciej
Received on Tuesday, 16 June 2009 12:37:57 UTC