Python Big-O Cheat Sheet

Definitions

Big-O notation

An upper bound on how an algorithm's cost grows as the input size n approaches infinity. Constants and lower-order terms are dropped, so O(2n + 5) is just O(n); it describes the shape of growth, not an exact operation count.

Time complexity

How the number of operations an algorithm performs grows with the input size. This is what the chart above plots: elements on the x-axis, operations on the y-axis.

Space complexity

How much extra memory an algorithm needs as the input grows, beyond the input itself. A pass that builds a new list of every element is O(n) space; one that mutates in place is O(1).

Time, Space, worst case

Time is the typical (average) cost and Space the extra memory. When the worst case is actually worse, it is called out in the Notes: a dict Get is O(1) time but O(n) worst under pathological hash collisions.

Amortized

The average cost per operation across a long sequence, even when one call is occasionally expensive. list.append is amortized O(1) (the * marker): almost every append is constant, and the rare O(n) resize is spread thin across all of them.

C-level vs Python-level (Runtime column)

Two operations with the same Big-O can differ 10–100× in wall-clock time. Built-ins marked "C" run inside CPython's compiled internals; code marked "Py" runs interpreted, one bytecode step at a time. Same growth curve, very different constant factor, which is why sum(x) beats a hand-written loop and "".join(parts) beats s += x.

n vs. k

n is the size of the whole input; k is the size of the part you touch (a slice, a sub-result). O(k) scales with that part, not the entire structure.

Complexity classes

Searching & sorting

Choosing a structure

Built-in containers

nums = [3, 1, 2]
nums.append(4)     # O(1)  -> [3, 1, 2, 4]
nums.sort()        # O(n log n)
nums[0]            # O(1)  -> 1

t = (1, 2, 3)
t[0]               # O(1)  -> 1
2 in t             # O(n)
d = {(0, 0): "origin"}   # tuple as a dict key

r = range(0, 1_000_000, 2)
len(r)              # O(1)  -> 500000
r[100]              # O(1)  -> 200
999_998 in r        # O(1)  (arithmetic, not a scan)

from array import array
a = array("i", [1, 2, 3])   # typed: signed int
a.append(4)                 # O(1)
a[0]                        # O(1)  -> 1

s = "hello"
s.upper()          # "HELLO" (new string)
s[0]               # "h"
"lo" in s          # True

b = b"hello"
b[0]                # O(1)  -> 104
b"lo" in b          # True
b.decode("utf-8")   # "hello"

ba = bytearray(b"hi")
ba.append(33)       # O(1)  -> bytearray(b'hi!')
ba[0] = 72          # O(1)
bytes(ba)           # back to immutable

d = {"a": 1}
d["b"] = 2         # insert, O(1)
d["a"]             # O(1)  -> 1
"a" in d           # True

from collections import defaultdict
groups = defaultdict(list)
groups["a"].append(1)   # no KeyError, O(1)
counts = defaultdict(int)
counts["x"] += 1

from collections import Counter
c = Counter("aabbbc")   # {'b':3,'a':2,'c':1}
c["a"]                  # 2
c.most_common(2)        # [('b',3),('a',2)]

s = {1, 2, 3}
s.add(4)           # O(1)
2 in s             # True
s & {2, 3, 9}      # {2, 3}

fs = frozenset({1, 2, 3})
2 in fs            # O(1)
fs | {4}           # new frozenset
seen = {fs}        # frozenset inside a set

from collections import deque
q = deque([1, 2, 3])
q.appendleft(0)    # O(1)
q.popleft()        # O(1)

import heapq
h = []
heapq.heappush(h, 3)
heapq.heappush(h, 1)
heapq.heappop(h)   # 1

import bisect
a = [1, 3, 5, 7]
bisect.bisect(a, 4)     # 2  (insertion point)
bisect.insort(a, 4)     # -> [1, 3, 4, 5, 7]

Language built-ins

len(xs)                    # O(1)
sum(x for x in xs)         # O(n)
sorted(xs, key=abs)        # O(n log n)
any(x > 0 for x in xs)     # O(n), stops at first hit

squares = [x*x for x in xs]      # list, O(n) space
total   = sum(x*x for x in xs)   # generator, O(1) space

Standard-library tools

from itertools import chain, product, permutations
list(chain([1, 2], [3, 4]))      # [1, 2, 3, 4]
list(product([0, 1], repeat=2))  # [(0,0),(0,1),(1,0),(1,1)]
list(permutations([1, 2, 3]))    # 6 tuples (3!)

from functools import lru_cache, reduce
@lru_cache
def fib(n): return n if n < 2 else fib(n-1) + fib(n-2)
reduce(lambda a, b: a + b, [1, 2, 3])   # 6

import copy
a = [[1, 2], [3, 4]]
b = copy.copy(a)        # outer list new, inner lists shared
c = copy.deepcopy(a)    # everything cloned

import math
math.gcd(12, 18)     # 6
math.isqrt(50)       # 7
math.factorial(5)    # 120

import random
random.choice([1, 2, 3])        # one item
random.shuffle(deck)            # in place
random.sample(range(100), 5)    # 5 unique

import statistics
statistics.mean([1, 2, 3])      # 2
statistics.median([3, 1, 2])    # 2
statistics.mode([1, 1, 2])      # 1

from collections import namedtuple
Point = namedtuple("Point", "x y")
p = Point(1, 2)
p.x        # O(1)  -> 1
p[0]       # O(1)  -> 1

from collections import OrderedDict
d = OrderedDict(a=1, b=2)
d.move_to_end("a")        # O(1)
d.popitem(last=False)     # O(1), pops the first item

from collections import ChainMap
defaults = {"color": "red", "size": "M"}
cm = ChainMap({"size": "L"}, defaults)
cm["size"]    # "L"  (first map wins)
cm["color"]   # "red"