Dictionary Operations
Operation | Examples | Complexity class | |
---|---|---|---|
Average case | Amortised Worst case | ||
Clear | d.clear() | O(1) | O(1) |
Construction | dict(…) | O(len(d)) | O(len(d)) |
Delete | del d[k] | O(1) | O(N) |
Get | d.get() | O(1) | O(N) |
Iteration(key, value, item) | for item in d: | O(N) | O(N) |
Length | len(d) | O(1) | O(1) |
Pop | d.pop(item) | O(1) | O(N) |
Pop Item | d.popitem() | O(1) | O(1) |
Returning Views | d.values() | O(1) | O(1) |
Returning keys | d.keys() | O(1) | O(1) |
Fromkeys | d.fromkeys(seq) | O(len(seq)) | O(len(seq)) |
Note: Defaultdict has operations same as dict with same time complexity as it inherits from dict.
Complexity Cheat Sheet for Python Operations
Python built-in data structures like list, sets, dictionaries provide a large number of operations making it easier to write concise code but not being aware of their complexity can result in unexpected slow behavior of your python code.
Prerequisite: List, Dictionaries, Sets
For example:
A simple dictionary lookup Operation can be done by either :
if key in d:
or
if dict.get(key)
The first has a time complexity of O(N) for Python2, O(1) for Python3 and the latter has O(1) which can create a lot of differences in nested statements.
Important points:
- Lists are similar to arrays with bidirectional adding and deleting capability.
- Dictionaries and Set use Hash Tables for insertion/deletion and lookup operations.
This Cheat sheet can be referred for choosing operations that are efficient with respect to time.
List Operations
Operation | Examples | Complexity class | |
---|---|---|---|
Average case | Amortised Worst case | ||
Append | l.append(item) | O(1) | O(1) |
Clear | l.clear() | O(1) | O(1) |
Containment | item in/not in l | O(N) | O(N) |
Copy | l.copy() | O(N) | O(N) |
Delete | del l[i] | O(N) | O(N) |
Extend | l.extend(…) | O(N) | O(N) |
Equality | l1==l2, l1!=l2 | O(N) | O(N) |
Index | l[i] | O(1) | O(1) |
Iteration | for item in l: | O(N) | O(N) |
Length | len(l) | O(1) | O(1) |
Multiply | k*l | O(k*N) | O(k*N) |
Min, Max | min(l), max(l) | O(N) | O(N) |
Pop from end | l.pop(-1) | O(1) | O(1) |
Pop intermediate | l.pop(item) | O(N) | O(N) |
Remove | l.remove(…) | O(N) | O(N) |
Reverse | l.reverse() | O(N) | O(N) |
Slice | l[x:y] | O(y-x) | O(y-x) |
Sort | l.sort() | O(N*log(N)) | O(N*log(N)) |
Store | l[i]=item | O(1) | O(1) |
For more information, refer to Internal working of list in Python.
Note: Tuples have the same operations (non-mutable) and complexities.
Contact Us