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
to describe how the running time of an operation grows with the size of its inputs. Unless stated otherwise, n denotes the number of elements currently in the container, and k is the value of a numeric parameter, such as an index or a repeat count.
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
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 (dell[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, otherwise O(n - i + len(t))
Delete slice (dell[i:j])
O(n - i)
Extend (l.extend(t))
O(len(t))
Sort (l.sort())
O(n log n)
Concatenate (l1+l2)
O(len(l1) + len(l2))
Multiply (l*k)
O(nk)
xinl
O(n)
min(l), max(l)
O(n)
Get length (len(l))
O(1)
tuple
A
is an
sequence. Because a tuple can never change, there are no insertion or deletion costs, and making a copy simply returns the same object, so is constant time (O(1)).
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(len(t1) + len(t2))
Multiply (t*k)
O(nk)
Iteration
O(n)
xint
O(n)
min(t), max(t)
O(n)
Get length (len(t))
O(1)
dict
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 are well-distributed among the set of possible 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. They also assume that hashing and comparing a key is O(1). For more detail on the implementation, see
How are dictionaries implemented in CPython?
.
Operation
Complexity
keyind
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 (deld[key], d.pop(key))
O(1)
Update (d.update(t), d|=t)
O(len(t))
Iteration
O(n)
Get length (len(d))
O(1)
set, frozenset
See
as the
and
implementations are similar, and the same caveats apply. In the worst case, O(1) operations instead take O(n) time, and operations that look up every element degrade accordingly.
A
is
, 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
xins
O(1)
Copy (s.copy())
O(n)
Add (s.add(x))
O(1)
Discard (s.discard(x), s.remove(x))
O(1)
Union (s1|s2, s1.union(s2))
O(len(s1) + len(s2))
Update (s1|=s2, s1.update(s2))
O(len(s2))
Intersection (s1&s2, s1.intersection(s2))
O(min(len(s1), len(s2)))
Intersection update (s1&=s2, s1.intersection_update(s2))
O(min(len(s1), len(s2)))
Difference (s1-s2, s1.difference(s2))
O(len(s1))
Difference update (s1-=s2, s1.difference_update(s2))
O(min(len(s1), len(s2)))
Symmetric difference (s1^s2, s1.symmetric_difference(s2))
O(len(s1) + len(s2))
Symmetric difference update (s1^=s2, s1.symmetric_difference_update(s2))
O(len(s2))
Get length (len(s))
O(1)
str, bytes, bytearray
and
objects are immutable sequences of characters and bytes, respectively. As with tuples, copying one returns the original object. A
is mutable, and additionally supports the mutating operations of
(except sort()), at the same costs. However, deleting at the front with del (delb[0], delb[:k]) 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(j - i)
Concatenate (s+t)
O(len(s) + len(t))
Multiply (s*k)
O(nk)
Substring search (xins, s.find(x), s.index(x))
O(n)
Reverse substring search (s.rfind(x), s.rindex(x))
O(n × len(x))
Encode or decode
O(n)
Iteration
O(n)
Get length (len(s))
O(1)
memoryview
objects allow Python code to access the internal data of an object that supports the
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)
Index (v.index(x))
O(n)
Count (v.count(x))
O(n)
Convert to bytes (v.tobytes(), bytes(v))
O(n)
Get length (len(v))
O(1)
range
A
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 (r[k])
O(1)
Get slice (r[i:j])
O(1)
xinr
O(1)
Index and count (r.index(x), r.count(x))
O(1)
Iteration
O(n)
min(r), max(r)
O(n)
Get length (len(r))
O(1)
Notes