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) |
frozenset |
Immutable unique items |
- |
- |
- |
Sequence Types
Mapping & Set Types
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) |
Timsort (≤3.10), Powersort (3.11+) |
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(k) for a custom __abs__() |
divmod() |
O(1) |
O(1) |
O(n²) for arbitrary-precision integers |
pow() |
O(log y) |
O(1) |
Fast exponentiation; 3-argument form stays modular |
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) |
n = length of the result |
repr() |
O(n) |
O(n) |
Recurses into containers |
ascii() |
O(n) |
O(n) |
Like repr(), escaping non-ASCII |
hash() |
O(k) |
O(1) |
O(n) for strings, cached after the first call |
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(d) |
O(1) |
Instance dict hit is O(1) average |
setattr() |
O(1) |
O(1) |
Hash table insertion |
hasattr() |
O(d) |
O(1) |
Same lookup as getattr(), exception caught |
delattr() |
O(1) |
O(1) |
Hash table deletion |
dir() |
O(n log n) |
O(n) |
Dominated by sorting the result |
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; lookup is 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 |
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 |
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 |
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(n) |
O(n) |
n = size of the introspected surface |
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 |
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