Python Operation Complexity

Scope — What every Python built-in and container operation actually costs, and why: the per-call tables for the built-in functions, list, str, dict/set, tuple, deque, heapq, bisect and int, the CPython layout each cost follows from, and the seven idioms that quietly turn an O(n) solution into an O(n²) one. See also: python_trick.md — the Python idioms these costs govern; complexity_cheatsheet.md — the same Big-O lookup for data structures and classic algorithms rather than for Python’s built-ins; python_trick_stdlib.md — heapq, bisect, collections and the rest of the library in depth; time_space_complexity.md — arguing the complexity of a whole LC solution rather than of one call; java_trick_collections.md — the same ground in Java.

LeetCode Problem Lists

• Python

Overview

Why this sheet exists: nearly every “your solution is O(n²), can you do better?” moment comes from a built-in whose cost was assumed to be O(1). len() really is free; x in my_list, res += ch and arr[1:] are not.

n = size of the object being operated on, m = size of the other operand, k = size of a slice.

Built-in functions

list — a dynamic array of pointers

A CPython list is a contiguous PyObject ** block plus a length and a capacity. Every element is one pointer wide, whatever it holds — that is why indexing is O(1) and why inserting in the middle has to memmove the tail.

list = [10, 20, 30]           capacity 4, size 3

  ob_size = 3   ─────────────► len() reads this, O(1)
  ob_item ──► [ *10 | *20 | *30 | ___ ]     <- contiguous pointers
                 ^                   ^
                 l[0] is one         spare slot from the
                 offset away         geometric over-allocation
                 -> O(1)             -> append() is amortized O(1)

  l.pop(0)  ->  [ *20 | *30 | ___ | ___ ]   <- everything memmove'd left: O(n)

str — an immutable array of code points

Strings are immutable, so every “modification” allocates a new string and copies. CPython stores them compactly (PEP 393: 1, 2 or 4 bytes per char depending on the largest code point), so s[i] is still O(1) indexing rather than a UTF-8 walk.

res = ""
for ch in s:          #  n iterations
    res += ch         #  each one allocates a buffer of the current length
                      #  1 + 2 + 3 + ... + n  =  O(n^2) bytes copied

parts = []
for ch in s:
    parts.append(ch)  #  amortized O(1) each
res = "".join(parts)  #  ONE allocation of exactly n bytes  ->  O(n) total

CPython does have an in-place += optimisation (when the string’s refcount is 1 it can realloc instead of copying), which sometimes hides the O(n²). Do not rely on it — it breaks the moment a second name points at the string, and it does not exist in PyPy/Jython. Say “join” in an interview.

dict and set — open-addressing hash tables ★★★★☆Priority 4 of 5 — High value — a gap here costs you rounds

Both are open-addressing tables (probe the next slot on a collision, no bucket chains). A dict since 3.6 is split: a sparse array of indices plus a dense array of (hash, key, value) entries in insertion order — which is where ordering guarantees and the compact memory come from.

The one-line version for an interview: a hash table buys O(1) membership by spending O(n) space. Turning x in nums (list, O(n)) into x in set(nums) (O(1)) is what collapses most brute-force O(n²) solutions to O(n) — and the set(nums) build is itself O(n).

Other containers worth knowing

The traps that actually cost interview points ★★★★★Priority 5 of 5 — Must know — expect it in almost every loop

# 1) membership on the wrong container  ->  O(n^2) instead of O(n)
for x in nums:
    if x in seen_list:   # ❌ O(n) each
        ...
seen = set(seen_list)    # ✅ O(n) once, then O(1) each

# 2) building a string with +=  ->  O(n^2)
res = ""
for ch in s: res += ch          # ❌
res = "".join(ch for ch in s)   # ✅

# 3) list as a queue  ->  O(n) per dequeue
q = [root]; node = q.pop(0)             # ❌ O(n) memmove every pop
from collections import deque
q = deque([root]); node = q.popleft()   # ✅ O(1)

# 4) slicing inside recursion  ->  O(n^2) time AND O(n^2) space
def f(arr):
    return f(arr[1:])            # ❌ a full copy per level
def f(arr, i):
    return f(arr, i + 1)         # ✅ pass an index

# 5) sorting inside a loop  ->  O(n^2 log n)
for w in words: key = "".join(sorted(w))   # ⚠️ fine (sorts each word once)
for i in range(n): arr.sort()              # ❌ sorts the WHOLE array n times

# 6) recomputing max/min/sum over the same window
for i in range(n): cur = max(nums[i:i+k])  # ❌ O(n*k) -> use a monotonic deque, O(n)

# 7) `in` on a dict's items vs keys
if k in d:            # ✅ O(1) — hashes the key
if k in d.keys():     # ✅ O(1) too — a view, not a list
if k in list(d):      # ❌ O(n) — materialises the keys first

What to say out loud: name the container, then the cost. “seen is a set, so the membership test is O(1) average — that makes the whole loop O(n) time and O(n) space.” Stating the container is what makes the complexity claim checkable, and it is exactly the sentence an interviewer is listening for.

See also complexity_cheatsheet.md for the same lookup at the level of data structures and classic algorithms, python_trick.md for the idioms these costs govern, and python_trick_stdlib.md for heapq / bisect / collections in depth.