Time complexity of operations on built-in types

This page documents the time-complexity of various operations on built-in types in CPython. Other Python implementations may have different performance characteristics. Additionally, the listed costs assume exact built-in types, as instances of subclasses may have different costs.

We use Big O notation to describe how the running time of an operation grows with the size of its input. Unless stated otherwise, n denotes the number of elements currently in the container, and k is either the value of a parameter or the number of elements in the parameter.

For a pragmatic approach to assessing time complexity, see Ned Batchelder’s Big-O: How Code Slows as Data Grows talk and blog post.

list

Lists are mutable sequences; for more detail on the implementation see How are lists implemented in CPython?. The largest costs come from growing 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 a collections.deque instead.

Operation	Complexity
Copy (s.copy())	O(n)
Append (s.append(x)) [1]	O(1)
Pop (s.pop(k)) [1] [2]	O(n - k)
Insert (s.insert(k, x)) [1] [2]	O(n - k)
Get item (s[k])	O(1)
Set item (s[k] = x)	O(1)
Delete item (del s[k]) [2]	O(n - k)
Iteration	O(n)
Get slice (s[i:j])	O(k)
Set slice (s[i:j] = t)	O(k + n)
Delete slice (del s[i:j])	O(n)
Extend (s.extend(t)) [1]	O(k)
Sort (s.sort()) [3]	O(n log n)
Multiply (s * k)	O(nk)
x in s	O(n)
min(s), max(s)	O(n)
Get length (len(s)) [4]	O(1)

tuple

A tuple is an immutable sequence. Because a tuple can never change, there are no insertion or deletion costs, and making a copy is constant time as the same object is returned.

Operation	Complexity
Copy (tuple(s))	O(1)
Get item (s[k])	O(1)
Get slice (s[i:j])	O(k)
Concatenate (s + t)	O(n + k)
Multiply (s * k)	O(nk)
Iteration	O(n)
x in s	O(n)
min(s), max(s)	O(n)
Get length (len(s)) [4]	O(1)

dict, frozendict

The times listed for dict objects are average-case times, as they assume the hash function for the objects is sufficiently robust to make collisions uncommon; they also assume the keys used in parameters are selected uniformly at random from the set of all keys. In the worst case, when every key hashes to the same value, each of the O(1) operations below instead takes O(n) time. For more detail on the implementation, see How are dictionaries implemented in CPython?.

A frozendict is immutable, so it does not support setting or deleting items; the other operations below apply to it at the same costs.

Operation	Complexity
key in d	O(1)
Copy (d.copy()) [5] [6]	O(n)
Get item (d[key])	O(1)
Set item (d[key] = value) [1]	O(1)
Delete item (del d[key])	O(1)
Iteration [6]	O(n)
Get length (len(d)) [4]	O(1)

set, frozenset

See dict as the set and frozenset implementations are intentionally very similar, and the same hash collision caveat applies. In the worst case, O(1) operations instead take O(n) time, and operations that look up every element of an operand degrade accordingly.

A frozenset is immutable, so it does not support adding, discarding, or the in-place update operations; the others below apply to it at the same costs.

Operation	Complexity
x in s	O(1)
Add (s.add(x)) [1]	O(1)
Discard (s.discard(x))	O(1)
Union (s | t) [6]	O(len(s) + len(t))
Intersection (s & t, s.intersection(t)) [6] [7]	O(min(len(s), len(t)))
Difference (s - t, s.difference(t)) [6] [8]	O(len(s))
Difference update (s.difference_update(t)) [1] [6] [7]	O(min(len(s), len(t)))
Symmetric difference (s ^ t) [6]	O(len(s) + len(t))
Symmetric difference update (s.symmetric_difference_update(t)) [1] [6]	O(len(t))
Get length (len(s)) [4]	O(1)

str, bytes, bytearray

str and bytes objects are immutable sequences of characters and bytes respectively; As with tuples, copying one returns the original object. A bytearray is mutable, and additionally supports the mutating operations of list (except sort()), at the same costs. However, deleting at the front only advances the start of the buffer instead of moving the remaining bytes, and is amortized O(1).

Operation	Complexity
Get item (s[k])	O(1)
Get slice (s[i:j])	O(k)
Concatenate (s + t)	O(n + k)
Multiply (s * k)	O(nk)
Substring search (x in s, s.find(x), s.index(x)) [9]	O(n)
Encode or decode	O(n)
Iteration	O(n)
Get length (len(s)) [4]	O(1)

memoryview

memoryview objects allow Python code to access the internal data of an object that supports the buffer protocol without copying. In particular, slicing a memory view returns a new view onto the same buffer.

Operation	Complexity
Create (memoryview(obj))	O(1)
Get item (v[k])	O(1)
Get slice (v[i:j])	O(1)
Convert to bytes (v.tobytes(), bytes(v))	O(n)
Get length (len(v)) [4]	O(1)

range

A range object computes its items on demand from its start, stop and step values, so most operations do not depend on the length of the range.

Operation	Complexity
Get item (s[k])	O(1)
Get slice (s[i:j])	O(1)
x in s [10]	O(1)
Index and count (s.index(x), s.count(x)) [10]	O(1)
Iteration	O(n)
min(s), max(s)	O(n)
Get length (len(s)) [4]	O(1)

Notes

[1] (1,2,3,4,5,6,7,8)

Amortized. An individual operation may occasionally be O(n) when the underlying storage is resized, but this cost is spread over many operations, depending on the history of the container.

[2] (1,2,3)

Popping or deleting the element at index k of a list of size n shifts all elements after k one slot to the left, moving n - k - 1 elements; inserting at index k shifts the elements from k onwards one slot to the right, moving n - k elements. The worst case is index 0, where the whole rest of the list has to be moved; the average case, an index in the middle of the list, takes O(n/2) = O(n) operations; and operating at the end of the list moves nothing and is O(1).

[3]

This is the worst case scenario. Sorting is adaptive and input that is already sorted or reverse-sorted takes only O(n) comparisons. See Objects/listsort.txt for more information.

[4] (1,2,3,4,5,6,7)

The number of elements is stored in the object, so len() does not need to count them.

[5]

Copying a frozendict is O(1) as it returns the original object.

[6] (1,2,3,4,5,6,7,8)

These operations scan the container’s internal hash table, which is not shrunk when elements are removed. After removing most elements, they still take time proportional to the container’s former size, until a later insertion triggers a resize.

[7] (1,2)

O(len(t)) if t is not a set.

[8]

O(len(s) + len(t)) if t is not a set.

[9]

A naive substring search would need O(nk) comparisons in the worst case, where k is the length of the substring searched for, but CPython uses search algorithms with a linear worst case for forward searches. See Objects/stringlib/stringlib_find_two_way_notes.txt for details.

[10] (1,2)

Assuming int or bool arguments. For other types, the range is searched like any other sequence in O(n) time.