BigO for dictionary method 'get(key)'

Question

Does anybody know what O(?) for python's dictionary 'get(key)' method?

I've tested it with cProfile module and get same results of time for 100, 1000, 10000, 100000, 1000000, 100000000 records in the dictionary.

Does it means that python's dictionary provides O(1) access time for any key?

Yes. Dictionaries are implemeted as hash key which have O(1) for lookup — karthikr, Jun 04 '13 at 20:00
possible duplicate of [Time complexity of accessing a Python dict](http://stackoverflow.com/questions/1963507/time-complexity-of-accessing-a-python-dict) — jamylak, Jun 04 '13 at 20:12
http://stackoverflow.com/questions/513882/python-list-vs-dict-for-look-up-table — jamylak, Jun 04 '13 at 20:20

score 6 · Accepted Answer · edited Jun 04 '13 at 20:29

6

The answer is - YES, because Python dicts use Hashes to store keys. And a hash table has O(1) average time complexity to access its keys - read more here http://en.wikipedia.org/wiki/Hash_table.

The worst case scenario for key retrieval is O(n), where n is the number of keys in the dictionary. (@Michael Butscher).

edited Jun 04 '13 at 20:29

answered Jun 04 '13 at 19:58

Morgan Wilde

16,795
10
53
99

1

Except for pathological cases with massive hash collisions. Worst case is O(n) where n is the number of keys – Michael Butscher Jun 04 '13 at 20:01
5

Worst case is very, very, very hard to reach though. – Ignacio Vazquez-Abrams Jun 04 '13 at 20:04
Thanks for catching that @MichaelButscher! Until you mentioned that, I was unaware that was even possible, because rainbow-tables are so successful one wouldn't suspect they would have a bottleneck. – Morgan Wilde Jun 04 '13 at 20:06
@IgnacioVazquez-Abrams Yes, except if someone uses his own class(es) for keys and writes a bad hash function (but this is not very likely either). – Michael Butscher Jun 04 '13 at 20:12
@MichaelButscher So that's implementing the `__hash__()` method for your custom objects, right? – Morgan Wilde Jun 04 '13 at 20:15
2

@MorganWilde yes, you would probably also need to implement `__eq__` too for proper checks (in case of hash collision) – jamylak Jun 04 '13 at 20:17
1

That's not *amortized* time complexity. Amortized complexity would mean: For any sequence of n operations on the dictionary, the *total* time is as if each operation took O(1) time - an individual operation may still take more time though. One example is appending to an over-allocating array, where appending. As http://wiki.python.org/moin/TimeComplexity notes, the correct term is *average*. – Jun 04 '13 at 20:24
@delnan I didn't have "amortized" in the original and I do feel that average suits this better, but I may be out of my depth... :) – Morgan Wilde Jun 04 '13 at 20:27
It doesn't suit better, it's simple correct whereas "amortized" is not. Hopefully the user who edited that in sees my explanation. I fixed it now. – Jun 04 '13 at 20:28

score 1 · Answer 2 · answered Jun 04 '13 at 19:59

1

Yes it is really O(1) for any key.

answered Jun 04 '13 at 19:59

Mike Müller

82,630
20
166
161

BigO for dictionary method 'get(key)'

2 Answers2