Posted on

# Time Complexity Analysis of Python Methods: Big(O) Notations for List, Tuple, Set, and Dictionary Methods

### 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.remove(element) O(1) O(1) O(1) or O(n) Average O(1), worst O(n)
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)