3

From the Python wiki on Time Complexity, following are the costs for performing operations on a dict.

Operation       Average Case    Amortized Worst Case
Copy[2]         O(n)            O(n)
Get Item        O(1)            O(n)
Set Item[1]     O(1)            O(n)
Delete Item     O(1)            O(n)
Iteration[2]    O(n)            O(n)

From my understanding of hash tables, the setting of a key, when the hashtable is full beyond the threshold value might result in resizing of the hash table, which means a worst case complexity of O(n) is possible.

But in which case can Getting or Deleteing an item have the Amortized Worst Case complexities of O(n)?

Anshul Goyal
  • 73,278
  • 37
  • 149
  • 186
  • 10
    Because all of the keys might have the same hash (or, rather, the same part of the hash that the dictionary uses to assign them to a *"bucket"*), in which case you're back to an `O(n)` trawl through all of them to find a match. – jonrsharpe Aug 28 '15 at 09:41
  • 1
    If you search for *"hash collision"*, you can find out more - see e.g. [this answer](http://stackoverflow.com/a/15192095/3001761). – jonrsharpe Aug 28 '15 at 09:47
  • 1
    *Worst* case is often a *degenerate* case: imagine all keys have a same hash, e.g. `0` – Dmitry Bychenko Aug 28 '15 at 09:50
  • @jonrsharpe Thanks! I was looking for a similar post which explained this, and have marked my question as a dupe now (the answer for that post would also answer this question) – Anshul Goyal Aug 28 '15 at 09:53
  • 1
    @mu無 no problem; I saw you'd proposed the dupe, so I've just used Mjölnir on it! – jonrsharpe Aug 28 '15 at 09:53
  • 1
    OP, @jonrsharpe I think you should re-open this question. The supposed duplicate was closed itself for being unclear. If you look at that question, although the answer is good, the question is at worst complete gibberish, and at best involves a lot of issues which are not in this question. It would make sense to have this specific question (which has an interesting and important answer) answered here in isolation. If these is a better dupe, please link to it. – jwg Aug 28 '15 at 09:56
  • @jwg Closed is better (from my POV). If someone lands up on my post in future, they will see the answer on the other one and their query will be solved, if they land there, this question is in the linked section so hopefully they can get the answer to either question. In any case, I already got the answer I was looking for. Don't mind a better dupe though. – Anshul Goyal Aug 28 '15 at 09:59

0 Answers0