http://qs321.pair.com?node_id=945058


in reply to Re^5: "Just use a hash": An overworked mantra?
in thread "Just use a hash": An overworked mantra?

Even if you manage to construct an insert sequence that, with a particular hash seed, results in Ω(N2) time to insert N keys, that still doesn't prove insertion isn't O(1) amortized time, with the amortization taken over all insert sequences, and/or all hash seeds.
  • Comment on Re^6: "Just use a hash": An overworked mantra?