Table of Content
- Big O Time Complexities of Python List and Tuples and its Methods
- Big O Time Complexities of Python Dictionary and its Methods
- Big O Time Complexities of Python Set and Frozen Set and its Methods
- Wrap Off
The built-in data structures in Python programming language like lists, sets, and dictionaries provide numerous operations making it easier to write concise code.
But, being unaware of their complexity while writing business logic or an algorithm can result in unexpected slow behavior of your python code.
In this lesson, you will learn about the various Big O Time Complexities of data structures in Python programming language such as Dictionary, List, and Sets as well as their methods.
Big O Time Complexities of Python List and Tuples and its Methods
In Python lists, values are assigned to and retrieved from specific, known memory locations.
Lists are similar to arrays, with bidirectional adding and deleting capability. Internally, a list is represented as an array.
The largest costs come from lengthening beyond the current allocation size (because everything must move), or from inserting or deleting somewhere near the beginning (because everything after that must move).
If you need to add or remove at both ends, consider using Python's collections.deque instead.
Tuples have the same operations and complexities as lists except for operations that mutate the list because tuples are immutable.
Here are the most important Big O time complexities to note in a Python list:
- For Indexing & Assigning, no matter how large the list is, index lookup and assignment take a constant amount of time and are thus O(1).
- For Appending & Concatenating, there is more than one way to do this, but we will focus on just two ways to do this. We can use the
appendmethod, which is O(1) or the concatenation operator (+), O(k), where k is the size of the concatenated list since k sequential assignment operations must occur. - For Popping, Shifting & Deleting, popping from a Python list is by default performed from the end or from a specific position by passing an index. When
popis called from the end, the operation is O(1), while callingpopfrom anywhere else is O(n). - For Iteration, it is O(n) because iterating over n elements requires n steps.
- The
inoperator in Python to determine whether an element is in a list is O(n) because we must iterate over every element. - For Slicing, slice access is O(k), where k is the size of the slice. Deleting a slice is O(n) for the same reason that deleting a single element is O(n) i.e n subsequent elements must be shifted toward the list's beginning.
- For Multiplying, multiplying a list is O(nk), since multiplying a k-sized list n times will require k(n−1) appends.
- For Reversing, it is O(n) since we must reposition each element.
- For Sorting, it is O(nlogn).
Here's a table summarizing the efficiencies of all dictionary operations in the table below:
| Operation | Big O Complexity | Worst Case | Example |
|---|---|---|---|
| copy | O(n) | O(n) | items.copy() |
| append | O(1) | O(1) | items.append(item) |
| extend | O(k) | O(k) | items.extend(…) |
| pop last with pop() | O(1) | O(1) | items.pop() |
| pop intermediate with pop(index) | O(n) | O(n) | items.pop(index) |
| get item | O(1) | O(1) | items(index) |
| set item | O(1) | O(1) | items(index)=item |
| insert item | O(n) | O(n) | items(index, item) |
| delete item | O(n) | O(n) | del items[index] |
| remove item | O(n) | O(n) | items.remove(…) |
| clear lists | O(1) | O(1) | items.clear() |
| Iteration | O(n) | O(n) | for item in items |
| Get slice | O(k) | O(k) | items[i:j] |
| Del slice | O(n) | O(n) | del items(i:j) |
| Set slice | O(k+n) | O(k+n) | |
| sort | O(nlogn) | O(nlogn) | items.sort() |
| Contains | O(n) | O(n) | item in/not in l |
| min(items), max(items) | O(n) | O(n) | min(items), max(items) |
| Get the length | O(1) | O(1) | len(items) |
| reverse | O(n) | O(n) | items.reverse() |
| Concatenate | O(k) | O(k) | items1+items2 |
| multiply | O(nk) | O(nk) | items1*items2 |
| List comparison | O(n) | O(n) | items1==items2 or items1!=items2 |
Big O Time Complexities of Python Dictionary and its Methods
Dictionaries use Hash Tables for insertion/deletion and lookup operations.
The Defaultdict in Python has operations similar to dict with the same time complexity as it inherits from dict.
Here are the most important Big O time complexities to note in a Python dictionary:
-
Accessing and adding an item in a dictionary are both O(1) operations.
-
Checking whether a key is present in a dictionary is also O(1) because checking for a given key is implicit in getting an item from a dictionary, which is itself O(1).
A simple dictionary lookup Operation can be done by either :
if key in d:
# Time complexity of O(N) for Python2, O(1) for Python3
or
if dict.get(key)
- Iterating over a dictionary is O(n) as well as copying the dictionary since n key/value pairs must be copied.
Here's a table summarizing the efficiencies of all dictionary operations in the table below:
| Operation | Big O Complexity | Worst Case | Example |
|---|---|---|---|
| construct new dict | O(len(d)) | O(len(d)) | dict() |
| check the size | O(1) | O(1) | len(d) |
| copy | O(n) | O(n) | d.copy() |
| get item | O(1) | O(n) | d.get() |
| set item | O(1) | O(n) | d[key]=item |
| delete item with key | O(1) | O(n) | del d[key] |
| delete item with pop() | O(1) | O(n) | d.pop(item) |
| delete item with popitem() | O(1) | O(n) | d.popitem() |
| clear() | O(1) | O(1) | d.clear() |
| contains(in) | O(1) | O(n) | item in/not in s |
| iteration | O(n) | O(n) | for item in d: |
| return values | O(1) | O(1) | d.values() |
| return keys | O(1) | O(1) | d.keys() |
| from keys | O(len(seq)) | O(len(seq)) | d.fromkeys(seq) |
Big O Time Complexities of Python Set and Frozen Set and its Methods
Set use Hash Tables for insertion/deletion and lookup operations.
Frozen Set have the same operations and complexities as sets except for operations that mutate the list because frozen sets are immutable.
Here's a table summarizing the efficiencies of all dictionary operations in the table below:
| Operation | Big O Complexity | Worst Case | Example |
|---|---|---|---|
| add item | O(1) | O(n) | s.add(item) |
| pop item | O(1) | O(n) | s.pop() |
| clear() | O(1) | O(1) | s.clear() |
| copy | O(n) | O(n) | s.copy() |
| contains(in) | O(1) | O(n) | item in/not in s |
| construct new set | O(len(s)) | O(len(s)) | set() |
| discard item | O(1) | O(n) | s.discard(item) |
| Set Comparison | O(min(len(s1), len(s2))) | O(min(len(s1), len(s2))) | s1==s2, s1!=s2 |
| iteration | O(n) | O(n) | for item in s: |
| check subset | O(len(s1)) | O(len(s1)) | s1<=s2 |
| check superset | O(len(s2)) | O(len(s1)) | s1>=s2 |
| Union | O(len(s1)+len(s2)) | - | s1+s2 |
| Intersection | O(min(len(s1), len(s2))) | O(len(s) * len(t)) | s1 & s2 |
| Difference | O(len(s)) | O(len(s)) | s1 -s2 |
| Difference Update | O(len(s2)) | – | s1.difference_update(s2) |
| Symmetric Difference | O(len(s1)) | O(len(s1) * len(s2)) | s1 ^ s2 |
| Symmetric Difference Update | O(len(s2)) | O(len(s2) * len(s1)) | s1.symmetric_difference_update(s2) |
Wrap Off
Python programming language is still progressing, which means that the above complexities could be subject to change.
The latest information on the performance of Python data types can be found on the Python website.
As of this writing, the Python wiki has a nice time complexity page that can be found at the Time Complexity Wiki.
If you learned from this tutorial, or it helped you in any way, please consider sharing and subscribing to our newsletter.
Please share this post and for more insightful posts on business, technology, engineering, history, and marketing, subscribe to our newsletter.