# What is Big O Time Complexities of Python List, Tuples, Dictionary, and Sets

Learn about the various Big O Time Complexities of Python Dictionary, Lists, and Sets as well as their methods.   Blank image with the text Big O Time Complexities of Python List, Tuples, Dictionary, and Sets

## Table of Content

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 `append` method, 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 `pop` is called from the end, the operation is O(1), while calling `pop` from anywhere else is O(n).
• For Iteration, it is O(n) because iterating over n elements requires n steps.
• The `in` operator 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:

OperationBig O ComplexityWorst CaseExample
copyO(n)O(n)items.copy()
appendO(1)O(1)items.append(item)
extendO(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 itemO(1)O(1)items(index)
set itemO(1)O(1)items(index)=item
insert itemO(n)O(n)items(index, item)
delete itemO(n)O(n)del items[index]
remove itemO(n)O(n)items.remove(…)
clear listsO(1)O(1)items.clear()
IterationO(n)O(n)for item in items
Get sliceO(k)O(k)items[i:j]
Del sliceO(n)O(n)del items(i:j)
Set sliceO(k+n)O(k+n)
sortO(nlogn)O(nlogn)items.sort()
ContainsO(n)O(n)item in/not in l
min(items), max(items)O(n)O(n)min(items), max(items)
Get the lengthO(1)O(1)len(items)
reverseO(n)O(n)items.reverse()
ConcatenateO(k)O(k)items1+items2
multiplyO(nk)O(nk)items1*items2
List comparisonO(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:

1. Accessing and adding an item in a dictionary are both O(1) operations.

2. 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 :

or

1. 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:

OperationBig O ComplexityWorst CaseExample
construct new dictO(len(d))O(len(d))dict()
check the sizeO(1)O(1)len(d)
copyO(n)O(n)d.copy()
get itemO(1)O(n)d.get()
set itemO(1)O(n)d[key]=item
delete item with keyO(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
iterationO(n)O(n)for item in d:
return valuesO(1)O(1)d.values()
return keysO(1)O(1)d.keys()
from keysO(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:

OperationBig O ComplexityWorst CaseExample
pop itemO(1)O(n)s.pop()
clear()O(1)O(1)s.clear()
copyO(n)O(n)s.copy()
contains(in)O(1)O(n)item in/not in s
construct new setO(len(s))O(len(s))set()
Set ComparisonO(min(len(s1), len(s2)))O(min(len(s1), len(s2)))s1==s2, s1!=s2
iterationO(n)O(n)for item in s:
check subsetO(len(s1))O(len(s1))s1<=s2
check supersetO(len(s2))O(len(s1))s1>=s2
UnionO(len(s1)+len(s2))-s1+s2
IntersectionO(min(len(s1), len(s2)))O(len(s) * len(t))s1 & s2
DifferenceO(len(s))O(len(s))s1 -s2
Difference UpdateO(len(s2))s1.difference_update(s2)
Symmetric DifferenceO(len(s1))O(len(s1) * len(s2))s1 ^ s2
Symmetric Difference UpdateO(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.

Next Tutorial — How to Solve Fibonacci Sequence in Python and Find the Big O ComplexityGet the Complete Code of Algorithms: Baby-Steps to Complete Mastery on Github.

## Connect with me.

Need an engineer on your team to grease an idea, build a great product, grow a business or just sip tea and share a laugh?