GeezerVison is showing pythoncomplexity.com — Builtins Overview - Python Big-O: Time & Space Complexity
Builtins Complexity¶
Everything Python gives you without an import: the built-in types, the built-in
functions, the constants, and the exception hierarchy. Each entry below links to a
page with the full breakdown; the tables here give the headline complexity so you
can find what you need at a glance.
Built-in Types¶
| Type |
Use Case |
Avg Access |
Avg Insert |
Avg Delete |
list |
Ordered sequences |
O(1) |
O(n) |
O(n) |
tuple |
Immutable sequence |
O(1) |
- |
- |
range |
Numeric sequences |
O(1) |
- |
- |
str |
Text |
O(1) |
- |
- |
bytes |
Binary data |
O(1) |
- |
- |
dict |
Key-value mapping |
O(1) |
O(1) |
O(1) |
set |
Unique items |
- |
O(1) |
O(1) |
frozendict |
Immutable key-value mapping (3.15+) |
O(1) |
- |
- |
frozenset |
Immutable unique items |
- |
- |
- |
Sequence Types¶
- List - Most flexible sequence type
- Tuple - Immutable sequences
- Range - Lazy numeric sequences
- String - Text and character sequences
- Bytes - Immutable binary data
- Bytearray - Mutable binary data, edited in place
Mapping & Set Types¶
- Dictionary - Hash-based key-value storage
- Set - Unordered unique items
- Frozendict - Immutable, hashable mapping (Python 3.15+)
- Frozenset - Immutable unique items
Numeric & Boolean Types¶
- Integer - Arbitrary-precision whole numbers
- Float - IEEE 754 double precision
- Boolean - Two singletons, a subclass of
int
Built-in Functions¶
Iteration¶
Functions in this group return an iterator. Creating it is cheap; the cost listed
under Notes is what you pay to consume it.
| Function |
Time |
Space |
Notes |
iter() |
O(1) |
O(1) |
Wraps an iterable in an iterator |
next() |
O(1)* |
O(1) |
* cost depends on the underlying iterator |
aiter() |
O(1) |
O(1) |
Async counterpart of iter() |
anext() |
O(1) |
O(1) |
Awaiting costs what the async generator costs |
enumerate() |
O(1) |
O(1) |
O(n) to consume; yields (index, item) tuples |
zip() |
O(1) |
O(1) |
O(n) to consume; stops at the shortest iterable |
map() |
O(m) |
O(m) |
m = input iterables; consuming n results costs O(n·m) plus n function calls |
filter() |
O(1) |
O(1) |
O(n*k) to consume, k = predicate time |
reversed() |
O(1) |
O(1) |
O(n) to consume; needs __reversed__, or __len__ and __getitem__ |
Aggregation & Ordering¶
| Function |
Time |
Space |
Notes |
len() |
O(1) |
O(1) |
Built-in containers cache their length |
sum() |
O(n) |
O(1) |
O(n²) if misused to concatenate strings |
min() |
O(n) |
O(1) |
Must compare every item |
max() |
O(n) |
O(1) |
Must compare every item |
sorted() |
O(n log n) |
O(n) |
Powersort |
all() |
O(n) |
O(1) |
Short-circuits on the first falsy item |
any() |
O(n) |
O(1) |
Short-circuits on the first truthy item |
Numbers & Bases¶
| Function |
Time |
Space |
Notes |
abs() |
O(1) |
O(1) |
O(n) for a negative int of n digits; a custom __abs__() sets its own cost |
divmod() |
O(1) |
O(1) |
O(n²) for arbitrary-precision integers |
pow() |
O(r²) |
Θ(r) |
r = bits of the result; the 3-argument form is O(log y * m²) in Θ(m) |
round() |
O(1) |
O(1) |
Exact halves round to even; round(x, ndigits) on a float is O(d²) time at worst and O(d) space in the d digits produced, and round(n, -k) on an int is O(b·k + k²) time and O(b + k) space in n's b bits |
bin() |
O(log n) |
O(log n) |
Cost is the length of the output |
hex() |
O(log n) |
O(log n) |
Cost is the length of the output |
oct() |
O(log n) |
O(log n) |
Cost is the length of the output |
Text & Characters¶
| Function |
Time |
Space |
Notes |
chr() |
O(1) |
O(1) |
Code point to character |
ord() |
O(1) |
O(1) |
Character to code point |
format() |
O(n) |
O(n + p) |
n = length of the result, p = precision; a decimal int costs O(n²), like str(), and an exact str neither padded nor truncated O(1) |
repr() |
O(L) |
O(L) |
L = result length, plus each element's repr; up to O(L × h) for nesting h deep, O(d²) for an int of d digits |
ascii() |
O(n) |
O(n) |
Like repr(), escaping non-ASCII |
hash() |
O(k) |
O(1) |
k = size of a built-in value, or the cost of its __hash__; str, bytes and frozenset keep the result, a tuple from 3.14 |
Objects, Attributes & Types¶
| Function |
Time |
Space |
Notes |
type() |
O(1) |
O(1) |
O(n + h) in the three-argument class-creating form, n = namespace entries, h = classes in the new MRO; several bases add the C3 merge |
isinstance() |
O(d) |
O(1) |
d = MRO length; O(1) on an exact type match |
issubclass() |
O(d) |
O(1) |
d = MRO length of the first argument; a match near the front returns early |
callable() |
O(1) |
O(1) |
Checks for __call__ |
id() |
O(1) |
O(1) |
Identity as an int; the memory address in CPython |
getattr() |
O(1) avg |
O(1) |
Cached per class and name; O(d) for a name built at run time, d = MRO depth |
setattr() |
O(1) |
O(1) |
Cached class lookup plus one store; O(s) for an ordinary attribute on a class, s = subclasses; more for a special method |
hasattr() |
O(1) avg |
O(1) |
The getattr() lookup with AttributeError caught; O(d) for a name built at run time |
delattr() |
O(1) |
O(1) |
Hash table deletion |
dir() |
O(k + p + n log n) |
O(n) |
Merges the class dictionaries, then sorts the names |
vars() |
O(1) |
O(1) |
Returns the __dict__ reference, no copy |
super() |
O(p) |
O(1) |
p = MRO position where the lookup stops; not cached, unlike obj.attr |
property() |
O(1) |
O(1) |
Descriptor creation and access |
classmethod() |
O(1) |
O(1) |
Descriptor creation; a cached lookup is O(1), a miss O(d) |
staticmethod() |
O(1) |
O(1) |
Descriptor creation; access returns the function itself |
Type Constructors¶
| Constructor |
Time |
Space |
Notes |
bool() |
O(1) |
O(1) |
Containers answer via __len__(), which is O(1) |
int() |
O(1) |
O(1) |
O(n²) parsing a very long numeric string |
float() |
O(1) |
O(1) |
O(n) from a string, with O(n) space for non-ASCII or underscored text; O(d) at worst from a d-digit int |
complex() |
O(1) |
O(1) |
O(n) from a string |
str() |
O(1) |
O(1) |
For an exact str, float, bool or None; O(d²) for an int of d digits, O(n) to decode bytes, O(L × h) plus each element's repr for a container, the cost of a custom __str__() |
bytes() |
O(n) |
O(n) |
n = length of the source; O(1) when it is an exact bytes |
bytearray() |
O(n) |
O(n) |
n = length of the source |
memoryview() |
O(1) |
O(1) |
A view over the buffer, never a copy |
list() |
O(n) |
O(n) |
n = length of the iterable |
tuple() |
O(n) |
O(n) |
O(1) when the argument is an exact tuple, not a subclass |
dict() |
O(n) |
O(n) |
O(n²) worst case with hash collisions |
set() |
O(n) |
O(n) |
O(n²) worst case with hash collisions |
frozenset() |
O(n) |
O(n) |
O(1) when the argument is an exact frozenset, not a subclass |
slice() |
O(1) |
O(1) |
Only stores indices; applying it costs O(k) for a type that copies the k items |
object() |
O(1) |
O(1) |
The base of every class |
sentinel() |
O(1) |
O(1) |
Python 3.15+; a unique named marker, compared with is |
Code Execution¶
| Function |
Time |
Space |
Notes |
eval() |
O(n + m) |
O(n + m) |
n = source length, m = evaluation cost |
exec() |
O(n + m) |
O(n + m) |
n = source length, m = execution cost |
compile() |
O(n) |
O(n) |
Parsing plus bytecode generation |
globals() |
O(1) |
O(1) |
Returns the existing module dict |
locals() |
O(1) |
O(1) |
In a function, m = names in its frame: O(m²) time from Python 3.13, O(m) before; O(m) space |
Input, Output & Debugging¶
| Function |
Time |
Space |
Notes |
print() |
O(n + k) |
O(m) |
n = characters written, k = arguments, m = longest converted argument; one write() per argument and separator |
input() |
O(k) |
O(k) |
k = length of the line read |
open() |
O(1)* |
O(b) |
* a system call; b = buffer size; reads and writes cost what they move |
help() |
O(D) |
O(D) |
D = documenting the object, which the page prices for each kind of object |
breakpoint() |
O(1) |
O(1) |
Hands control to the debugger |
Constants¶
| Constant |
Time |
Space |
Notes |
None |
O(1) |
O(1) |
Singleton; compare with is |
True |
O(1) |
O(1) |
Singleton bool |
False |
O(1) |
O(1) |
Singleton bool |
NotImplemented |
O(1) |
O(1) |
Returned by a special method to decline the operation |
Ellipsis |
O(1) |
O(1) |
The ... singleton |
__debug__ |
O(1) |
O(1) |
Folded in at compile time; -O drops the code it guards |
Exceptions & Interpreter¶
Key Concepts¶
Amortized Complexity¶
Some operations like list.append() have amortized O(1) complexity. This means:
- Most append operations are O(1)
- Occasionally, a resize happens requiring O(n)
- Over many operations, the average is O(1)
Lazy vs Eager¶
Several built-in functions return an iterator rather than a result. Calling them is
O(1) no matter how large the input; the real work happens as you consume the
iterator, and it never happens at all for items you skip. Wrapping the call in
list() makes it eager again and restores the O(n) space cost.
Implementation Details¶
CPython uses:
- Lists: Dynamic arrays with over-allocation
- Dicts: Hash tables with open addressing
- Sets: Hash tables (similar to dicts)
Version Notes¶
Different Python versions have optimizations:
- Python 3.7+: Dict insertion order guaranteed (language spec)
- Python 3.9+: New dict implementation improvements
- Python 3.10+: Additional optimizations for common operations
See Versions for detailed changelog by release.
See Also¶
|