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
