Introduction:
Whether you're working on real-world software or tackling problems in interviews, it's not just about writing code; it's all about writing efficient and scalable code. So, understanding the time complexity of your code becomes essential. In this article, we'll break down the Python methods for lists, tuples, sets, and dictionaries.
Don't worry, if you aren't familiar with the terminologies used in this analysis, I’ll shed light on every concept.
Time Complexity:
Time complexity measures the efficiency of an algorithm, and provides insights into how the execution time changes as the problem size increases.
Big(O) Notation:
The time complexity of a function is measured in Big(O) notations that give us information about how fast a function grows subject to input sizes.
The following are different notations with examples while calculating the time complexity of any piece of code:
- O(1): Imagine your friend is waiting for you at a specific restaurant in your street, and you’re already familiar with each restaurant in your street. Regardless of how many other restaurants there are, you always go to that specific restaurant where your friend is since you know exactly where to go.
- O(log n): Assume you are in a market with restaurants, each arranged by price from high to low. With a limited budget, you aim to find the best restaurant. Employing a binary search strategy, you start in the middle, navigate based on your budget, and repeat the process until you discover the desired restaurant.
- O(n): In the market, find all restaurants where there are more than 10 people. You need to visit each restaurant and count the number of people.
- O(n log n): Imagine a scenario where there's a mix-up of restaurants. Initially, you make a list of price ranges for all restaurants along with their names. Subsequently, you perform a search for your desired restaurant within this sorted list.
- O(n2): You want to find the best restaurant by comparing the quality of food with every other restaurant. So, for each restaurant, you have to go through all other restaurants and make comparisons.
Image taken from https://www.bigocheatsheet.com/
Timsort algorithm:
Tim Sort is the default sorting algorithm used by Python’s sorted() and list.sort() functions. It has the time complexity of O(n log n). It is a hybrid sorting algorithm derived from merge sort and insertion sort.
Amortized constant time:
It's used when mostly the operation is fast, but on some occasions, the operation of the algorithm is slow. It can be ignored in most cases.
For example, list.append(). As the list reserves some memory, so until it is utilized, list.append() gives O(1). However, when the reserved memory is filled, and new memory is required, a new list is created with more space, copying all elements. While this operation is not always constant time, it happens infrequently. So, we refer to it as Amortized constant time.
IN Operator:
The IN Operator uses linear search with a time complexity of O(n).
Python List Methods:
| Operation | Best Case | Average Case | Worst Case | Notes |
|---|---|---|---|---|
| append() | O(1) | O(1) | O(1) | Amortized constant time |
| insert() | O(1) | O(n) | O(n) | |
| pop() | O(1) | O(1) | O(1) | Amortized constant time |
| pop(index) | O(1) | O(n) | O(n) | |
| del list[index] | O(1) | O(n) | O(n) | Similar to pop(index) |
| extend() | O(1) | O(k) | O(k) | Where k is the length of the iterable |
| remove() | O(1) | O(n) | O(n) | Linear search |
| index() | O(1) | O(n) | O(n) | Linear search |
| count() | O(1) | O(n) | O(n) | Linear search |
| reverse() | O(1) | O(n) | O(n) | |
| sort() | O(n log n) | O(n log n) | O(n log n) | Timsort algorithm |
| copy() | O(n) | O(n) | O(n) | Shallow copy |
| clear() | O(1) | O(1) | O(1) | |
| index(x, start, end) | O(1) | O(n) | O(n) | Linear search within specified indices |
| Slice | O(1) | O(k) | O(k) | Where k is the size of the slice |
Python Tuple Methods:
| Operation | Best Case | Average Case | Worst Case | Notes |
|---|---|---|---|---|
| Creating a Tuple | O(1) | O(n) | O(n) | Where n is length of iterable |
| Indexing | O(1) | O(1) | O(1) | |
| Slicing | O(1) | O(b - a) | O(b - a) | |
| Concatenation | O(1) | O(k) | O(k) | Where k is the size of the tuple |
| tuple.index(element) | O(1) | O(n) | O(n) | Linear search |
| tuple.count(element) | O(1) | O(n) | O(n) | Linear search |
| element in tuple | O(1) | O(n) | O(n) | Linear search |
| Iterating | O(1) | O(n) | O(n) | Where n is length of the tuple |
Python Dictionary Methods:
| Operation | Best Case | Average Case | Worst Case | Notes |
|---|---|---|---|---|
| get(key) | O(1) | O(1) | O(1) | Constant time on average |
| pop(key) | O(1) | O(1) | O(1) | |
| popitem() | O(1) | O(1) | O(1) | |
| keys() | O(1) | O(1) | O(1) | Returns dynamic view with constant time |
| values() | O(1) | O(1) | O(1) | Returns dynamic view with constant time |
| items() | O(1) | O(1) | O(1) | Returns dynamic view with constant time |
| update() | O(n) | O(n) | O(n) | Merging two dictionaries |
| clear() | O(1) | O(1) | O(1) | |
| copy() | O(n) | O(n) | O(n) | Shallow copy |
| del dictionary[key] | O(1) | O(1) | O(1) | |
| key in dictionary | O(1) | O(1) | O(1) | Constant time on average |
| clear() | O(1) | O(1) | O(1) |
Python Set Methods:
| Operation | Best Case | Average Case | Worst Case | Notes |
|---|---|---|---|---|
| Creating a Set | O(1) | O(len(iterable)) | O(len(iterable)) | |
| s.add(element) | O(1) | O(1) | O(1) | |
| s.remove(element) | O(1) | O(1) | O(1) or O(n) | Average O(1), worst O(n) |
| s.discard(element) | O(1) | O(1) | O(1) | |
| s.pop() | O(1) | O(1) or O(n) | O(1) or O(n) | Average O(1), worst O(n) |
| s.clear() | O(1) | O(1) | O(1) | |
| s.copy() | O(len(s)) | O(len(s)) | O(len(s)) | Shallow copy |
| Iterating | O(1) | O(n) | O(n) | Where n is size of the set |
| element in s | O(1) | O(1) | O(1) | |
| Union (s1 | s2 or s1.union(s2)) | O(len(s1) + len(s2)) | O(len(s1) + len(s2)) | |
| Intersection (s1 & s2 or s1.intersection(s2)) | O(min(len(s1), len(s2))) | O(min(len(s1), len(s2))) | ||
| len(s) | O(1) | O(1) | O(1) |
Thanks for reading! Feel free to like, comment, and share if you find this article valuable.
You can check my other articles as well:
Mastering Metaclasses in Python using real-life scenarios
Use Asynchronous Programming in Python: Don’t Block Entire Thread
Top comments (0)