Computational Complexity of Python's Built-in Data Structures

This guide outlines the time complexity for various operations performed on the built-in types within CPython.

[!IMPORTANT] Please note that other Python implementations (like PyPy or Jython) may exhibit different performance profiles. Furthermore, these metrics apply to the base built-in types; subclassed versions may incur additional overhead.

Mathematical Notation

To describe how execution time scales relative to input size, we utilize Big O notation.

$n$ : The current number of elements stored in the container.
$k$ : A numeric parameter (e.g., an index or a repetition factor).

Type Hierarchy Overview

The following diagram illustrates the relationship between the types discussed in this document:

1. Lists (`list`)

Lists are implemented as mutable sequences. The most expensive operations typically involve:

Resizing: When the list grows beyond its allocated capacity, all elements must be relocated.
Shifting: Inserting or removing elements near the start of the list forces all subsequent elements to move.

~~If you need fast additions/removals at both ends, use a list.~~ $\rightarrow$ Correction: Use collections.deque instead.

Operation	Complexity
Copy (`l.copy()`)	$O(n)$
Append (`l.append(x)`)	$O(1)$
Pop (`l.pop(k)`)	$O(n - k)$
Insert (`l.insert(k, x)`)	$O(n - k)$
Get Item (`l[k]`)	$O(1)$
Set Item (`l[k] = x`)	$O(1)$
Delete Item (`del l[k]`)	$O(n - k)$
Iteration	$O(n)$
Get Slice (`l[i:j]`)	$O(j - i)$
Set Slice (`l[i:j] = t`)	$O(j - i)$ if `len(t) == j - i`, else $O(n - i + \text{len}(t))$
Delete Slice (`del l[i:j]`)	$O(n - i)$
Extend (`l.extend(t)`)	$O(\text{len}(t))$
Sort (`l.sort()`)	$O(n \log n)$
Concatenate (`l1 + l2`)	$O(\text{len}(l1) + \text{len}(l2))$
Multiply (`l * k`)	$O(nk)$
Membership (`x in l`)	$O(n)$
`min(l)`, `max(l)`	$O(n)$
Length (`len(l)`)	$O(1)$

2. Tuples (`tuple`)

Tuples are immutable sequences. Because they cannot be altered after creation, there are no costs associated with insertion or deletion. Copying a tuple is a constant-time operation because it simply returns a reference to the same object.

Operation	Complexity
Copy (`tuple(t)`)	$O(1)$
Get Item (`t[k]`)	$O(1)$
Get Slice (`t[i:j]`)	$O(j - i)$
Concatenate (`t1 + t2`)	$O(\text{len}(t1) + \text{len}(t2))$
Multiply (`t * k`)	$O(nk)$
Iteration	$O(n)$
Membership (`x in t`)	$O(n)$
`min(t)`, `max(t)`	$O(n)$
Length (`len(t)`)	$O(1)$

3. Dictionaries and Frozendicts (`dict`, `frozendict`)

The complexities for dict are average-case scenarios. They assume:

The hash function is robust (minimizing collisions).
Keys are distributed evenly.

Worst-Case Scenario: If every key hashes to the same value, $O(1)$ operations degrade to $O(n)$ . frozendict is the immutable version and does not support modification.

Operation	Complexity
Membership (`key in d`)	$O(1)$
Copy (`d.copy()`)	$O(n)$
Get Item (`d[key]`, `d.get(key)`)	$O(1)$
Set Item (`d[key] = value`)	$O(1)$
Delete Item (`del d[key]`, `d.pop(key)`)	$O(1)$
Update (`d.update(t)`, `d \|= t`)	$O(\text{len}(t))$
Iteration	$O(n)$
Length (`len(d)`)	$O(1)$

4. Sets and Frozensets (`set`, `frozenset`)

Sets share the same underlying implementation as dictionaries. Consequently, the same caveats regarding hash collisions and worst-case $O(n)$ performance apply. frozenset is immutable.

Operation	Complexity
Membership (`x in s`)	$O(1)$
Copy (`s.copy()`)	$O(n)$
Add (`s.add(x)`)	$O(1)$
Discard/Remove (`s.discard(x)`, `s.remove(x)`)	$O(1)$
Union (`s1 \| s2`, `s1.union(s2)`)	$O(\text{len}(s1) + \text{len}(s2))$
Update (`s1 \|= s2`, `s1.update(s2)`)	$O(\text{len}(s2))$
Intersection (`s1 & s2`, `s1.intersection(s2)`)	$O(\min(\text{len}(s1), \text{len}(s2)))$
Intersection Update (`s1 &= s2`, `s1.intersection_update(s2)`)	$O(\min(\text{len}(s1), \text{len}(s2)))$
Difference (`s1 - s2`, `s1.difference(s2)`)	$O(\text{len}(s1))$
Difference Update (`s1 -= s2`, `s1.difference_update(s2)`)	$O(\min(\text{len}(s1), \text{len}(s2)))$
Symmetric Diff (`s1 ^ s2`, `s1.symmetric_difference(s2)`)	$O(\text{len}(s1) + \text{len}(s2))$
Symm. Diff Update (`s1 ^= s2`, `s1.symmetric_difference_update(s2)`)	$O(\text{len}(s2))$
Length (`len(s)`)	$O(1)$

5. Strings, Bytes, and Bytearrays (`str`, `bytes`, `bytearray`)

str and bytes are immutable. bytearray is mutable and supports most list operations at similar costs.

Special Note on bytearray: Deleting from the front (e.g., del b[0]) is an amortized $O(1)$ operation because it simply shifts the buffer's start pointer rather than moving all data.

(Visual representation of data types)

Operation	Complexity
Get Item (`s[k]`)	$O(1)$
Get Slice (`s[i:j]`)	$O(j - i)$
Concatenate (`s + t`)	$O(\text{len}(s) + \text{len}(t))$
Multiply (`s * k`)	$O(nk)$
Substring Search (`x in s`, `s.find(x)`)	$O(n)$
Reverse Substring Search (`s.rfind(x)`)	$O(n \times \text{len}(x))$
Encode/Decode	$O(n)$
Iteration	$O(n)$
Length (`len(s)`)	$O(1)$

6. Memoryview (`memoryview`)

memoryview allows access to the internal data of buffer-protocol objects without copying the data. Slicing a memoryview creates a new view of the same buffer rather than a new copy.

# Example of memoryview usage
data = bytearray(b"Hello World")
view = memoryview(data)
sub_view = view[0:5] # O(1) operation

Operation	Complexity
Create (`memoryview(obj)`)	$O(1)$
Get Item (`v[k]`)	$O(1)$
Get Slice (`v[i:j]`)	$O(1)$
Index (`v.index(x)`)	$O(n)$
Count (`v.count(x)`)	$O(n)$
Convert to bytes (`v.tobytes()`)	$O(n)$
Length (`len(v)`)	$O(1)$

7. Range (`range`)

A range object is a lazy sequence; it calculates values on the fly using its start, stop, and step parameters. Consequently, most of its operations are independent of the range's total length.

Summary Checklist for Developers

Use deque for $O(1)$ pops/appends at both ends.
Be mindful of $O(n)$ worst-case scenarios in dict and set.
Use memoryview to avoid expensive $O(n)$ slicing of large buffers.
Remember that tuple copies are $O(1)$ .

Computational Complexity of Python's Built-in Data Structures

Mathematical Notation

Type Hierarchy Overview

1. Lists (list)

2. Tuples (tuple)

3. Dictionaries and Frozendicts (dict, frozendict)

4. Sets and Frozensets (set, frozenset)

5. Strings, Bytes, and Bytearrays (str, bytes, bytearray)

6. Memoryview (memoryview)

7. Range (range)