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(1) |
O(1) |
O(n*k) to consume, k = function time |
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 __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) |
Banker's rounding on exact halves |
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(n) |
O(n) |
Recurses into containers |
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) in the three-argument class-creating form |
isinstance() |
O(d) |
O(1) |
d = MRO depth; effectively O(1) in practice |
issubclass() |
O(d) |
O(1) |
d = MRO depth; effectively O(1) in practice |
callable() |
O(1) |
O(1) |
Checks for __call__ |
id() |
O(1) |
O(1) |
Backs the is operator |
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) |
Hash table insertion |
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(d) |
O(d) |
Walks the MRO, which is cached |
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; lookup is O(d) |
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) |
O(n) for containers and 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 already a tuple |
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 already a frozenset |
slice() |
O(1) |
O(1) |
Only stores indices; applying it costs O(k) |
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) |
O(m) in optimized function scopes |
| Function |
Time |
Space |
Notes |
print() |
O(n) |
O(n) |
n = total output length; I/O dominates |
input() |
O(k) |
O(k) |
k = length of the line read |
open() |
O(1)* |
O(1) |
* a system call; 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 operators that decline |
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