Python Time and Space Complexity Cheat Sheet

This page contains a condensed overview of the time and space costs of Python’s built-in data structures and standard library tools. It covers Big O basics, lists and strings, dictionaries and sets, stacks and queues, heaps, sorting and binary search, and recursion with caching. You can also download the information as a printable cheat sheet:

Free Bonus: Python Time and Space Complexity Cheat Sheet

Get a Python Time and Space Complexity Cheat Sheet (PDF) with the Big O costs of lists, dicts, sets, deques, heaps, sorting, and recursion on one page:

Python Time and Space Complexity Cheat Sheet

Practice with hands‑on coding exercises and put these costs to work in the Coding Interview Practice learning path.

New to Big O?

Reading Big O

  • Big O describes how work grows with the input size n
  • Drop constants and smaller terms: 3n + 5 is O(n)
  • Dict and set costs are averages, not guarantees
  • Extra space counts what you allocate, not the input or the returned output
Big O Name Example
O(1) Constant d[key], lst[-1]
O(log n) Logarithmic Binary search
O(n) Linear x in lst, sum(lst)
O(n log n) Linearithmic sorted(lst)
O(n²) Quadratic Nested loops over n
O(2ⁿ) Exponential Every subset
Python Spot the Hidden Loop 
for x in items:
    if x in seen_list:  # O(n): O(n²) total
        ...
    if x in seen_set:   # O(1): O(n) total
        ...

Want to go deeper on Big O?

Lists and Strings

  • Lists are fast at the end and slow at the front
  • Slices and + build new objects: O(k) time and space
  • Strings are immutable, so build them with .join()
Python Constant Time 
lst[i]           # O(1)
lst[i] = x       # O(1)
lst.append(x)    # O(1) amortized
lst.pop()        # O(1)
len(lst)         # O(1)
Python Linear Time 
x in lst         # O(n)
lst.index(x)     # O(n)
lst.insert(0, x) # O(n), shifts items
lst.pop(0)       # O(n), shifts items
min(lst)         # O(n)
Python Copies Cost Time and Space 
lst[a:b]         # O(b - a)
lst[::-1]        # O(n), new list
lst + other      # O(n + m)
lst.copy()       # O(n)
reversed(lst)    # O(1) to create
Python Build Strings in O(n) 
s = ""
for word in words:
    s += word    # Can copy s every time
s = "".join(words)  # O(n)

Why does join() win?

Dicts, Sets, and Counter

  • Lookups, inserts, and deletes take O(1) on average
  • k stored entries cost O(k) extra space
  • Keys must be hashable: tuples work, lists don’t
Python Dictionary 
d[key] = value   # O(1)
d.get(key, 0)    # O(1)
key in d         # O(1)
del d[key]       # O(1)
for k, v in d.items():  # O(n)
    ...
Python Set 
seen.add(x)      # O(1)
x in seen        # O(1)
a | b            # O(len(a) + len(b))
a & b            # O(min(len(a), len(b)))
a - b            # O(len(a))
Python Counter 
>>> from collections import Counter
>>> counts = Counter("banana")  # O(n)
>>> counts["a"]
3
>>> counts.most_common(1)  # O(n log k)
[('a', 3)]

Think you know your hash tables?

Stacks and Queues

  • A list is a fine stack: push and pop at the end
  • Use a deque for queues: O(1) at both ends
  • Indexing into the middle of a deque is O(n)
Python List as a Stack 
stack = []
stack.append("(")  # Push: O(1)
stack[-1]          # Peek: O(1)
stack.pop()        # Pop: O(1)
Python deque as a Queue 
from collections import deque
queue = deque(["a", "b"])
queue.append("c")      # O(1)
queue.popleft()        # O(1), 'a'
queue.appendleft("z")  # O(1)

Want to go deeper on stacks and queues?

Heaps With heapq

  • heap[0] is always the smallest item
  • A heap isn’t sorted: each parent is at most its children
  • For a max-heap, push negated numbers or use the _max functions (3.14+)
Python Core Operations 
import heapq
heapq.heapify(nums)      # O(n), in place
heapq.heappush(nums, x)  # O(log n)
heapq.heappop(nums)      # O(log n)
nums[0]                  # O(1), smallest
Python Top k Items 
heapq.nlargest(k, nums)   # O(n log k)
heapq.nsmallest(k, nums)  # O(n log k)
Python Keep a Size-k Heap 
heap = []
for x in stream:
    heapq.heappush(heap, x)  # O(log k)
    if len(heap) > k:
        heapq.heappop(heap)
heap[0]  # Kth largest so far

Ready to test yourself on heaps?

Sorting and Searching

  • Sorting takes O(n log n) time and O(n) extra space
  • The sort is stable: equal keys keep their order
  • Binary search needs sorted input
Python Sort 
sorted(nums)   # New list, O(n log n)
nums.sort()    # In place, O(n log n)
sorted(pairs, key=lambda p: p[1])
Python bisect 
>>> from bisect import bisect_left, insort
>>> nums = [1, 3, 3, 7]
>>> bisect_left(nums, 3)  # O(log n)
1
>>> insort(nums, 5)  # O(n), shifts items
Python Binary Search by Hand 
left, right = 0, len(nums)
while left < right:  # O(log n)
    mid = (left + right) // 2
    if nums[mid] < target:
        left = mid + 1
    else:
        right = mid
# Result: left is the first index >= target

Where do off-by-one bugs hide?

Recursion and Caching

  • Recursion depth d costs O(d) stack space
  • The default recursion limit is 1000
  • Pass indices instead of slices to avoid copies
  • A cache costs one entry per distinct argument
Python Indices, Not Slices 
def total(nums, i=0):  # O(n) time
    if i == len(nums):  # O(n) stack
        return 0
    return nums[i] + total(nums, i + 1)
Python Memoize With @cache 
from functools import cache

@cache
def stairs(n):  # O(n) time and space
    if n <= 1:
        return 1
    return stairs(n - 1) + stairs(n - 2)

stairs(30)  # 1346269

Still fuzzy on stack space?

Ready to go beyond the cheat sheet?

You can download this information as a printable cheat sheet:

Free Bonus: Python Time and Space Complexity Cheat Sheet

Get a Python Time and Space Complexity Cheat Sheet (PDF) with the Big O costs of lists, dicts, sets, deques, heaps, sorting, and recursion on one page:

Python Time and Space Complexity Cheat Sheet