Complexity

def contains(haystack_set, needle):
    return needle in haystack_set

Average O(1) hash lookup. (Worst-case O(n) on degenerate hashing.)

def bsearch(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target: return mid
        if nums[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

Search space halves each iteration.

def power(x, n):
    if n == 0: return 1
    half = power(x, n // 2)
    if n % 2 == 0:
        return half * half
    return half * half * x

T(n) = T(n/2) + O(1): one recursive call on half the exponent, counting each multiplication as O(1). The stack depth is log n.

def total(nums):
    s = 0
    for x in nums:
        s += x
    return s

One pass over the input; constant accumulator.

def two_sum_sorted(nums, target):
    l, r = 0, len(nums) - 1
    while l < r:
        s = nums[l] + nums[r]
        if s == target: return [l, r]
        if s < target: l += 1
        else: r -= 1
    return []

Pointers advance toward each other; combined work is O(n).

def min_val(nums):
    return min(nums)

min() scans the iterable.

def work(n):
    ops = 0
    size = 1
    while size < n:
        for _ in range(size):
            ops += 1
        size *= 2
    return ops

The inner loop runs 1 + 2 + 4 + ... up to n, a geometric series that sums to under 2n. The log n outer iterations don't multiply in because the inner work is dominated by the last pass.

import heapq
def three_smallest(nums):
    heapq.heapify(nums)
    return [heapq.heappop(nums) for _ in range(3)]

heapify is O(n) because most nodes sit near the bottom and sift down only a few levels. Three pops add 3 × O(log n). It rearranges nums in place.

def min_len(nums, target):  # nums are positive
    best, total, left = float("inf"), 0, 0
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

The while loop looks nested, but left only moves forward and never passes n, so it runs at most n times across the whole function. Each element enters and leaves the window once.

def fib(n, memo={}):
    if n < 2: return n
    if n in memo: return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

Each subproblem solved once; memo table + call stack = O(n).

def has_dup(nums):
    seen = set()
    for x in nums:
        if x in seen: return True
        seen.add(x)
    return False

Single pass + hash set of up to n elements.

def squares(n):
    out = []
    for i in range(n):
        out.append(i * i)
    return out

Each append is amortized O(1): the list grows its capacity geometrically, so all resize copies add up to a constant times n. The output list is O(n).

def shrink(a):
    if len(a) <= 1: return sum(a)
    total = sum(a)
    return total + shrink(a[: len(a) // 2])

T(n) = T(n/2) + n: the sum and slice cost n, then n/2, then n/4, a geometric series under 2n. The slices alive on the stack also sum to under n.

def group_codes(codes):
    # every code is exactly 6 characters
    groups = {}
    for c in codes:
        key = "".join(sorted(c))
        groups.setdefault(key, []).append(c)
    return list(groups.values())

The sort inside the loop runs on 6 characters every time, so it's O(1) per code. With unbounded word length k it would be O(n × k log k). The map holds every code.

String join(List<String> parts) {
    StringBuilder sb = new StringBuilder();
    for (String p : parts) {
        sb.append(p);
    }
    return sb.toString();
}

n = total characters. StringBuilder appends into a growable buffer that doubles when full, so each character is copied an amortized constant number of times. Compare String += in a loop, which recopies everything each time for O(n^2).

from collections import deque
def bfs(graph, src):
    seen = {src}
    q = deque([src])
    while q:
        node = q.popleft()
        for n in graph[node]:
            if n not in seen:
                seen.add(n); q.append(n)
    return seen

n = vertices, m = edges. Visits each vertex/edge once; queue + visited set are O(n).

def has_close_pair(nums, k):
    nums.sort()
    for i in range(len(nums) - 1):
        if nums[i+1] - nums[i] <= k:
            return True
    return False

Sort dominates; the scan is O(n). In-place sort uses O(1) auxiliary (ignoring Python's Timsort buffer).

def count_steps(n):
    steps = 0
    for i in range(n):
        j = 1
        while j < n:
            j *= 2
            steps += 1
    return steps

The outer loop runs n times; the inner loop doubles j until it reaches n, which takes log n steps. n × log n total.

def count_multiples(n):
    total = 0
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            total += 1
    return total

The inner loop runs n/i times, so the total is n/1 + n/2 + ... + n/n = n × H(n), and the harmonic number H(n) grows like ln n. This is the sieve of Eratosthenes shape.

def best(a, lo, hi):
    if lo == hi: return a[lo]
    mid = (lo + hi) // 2
    left, right = best(a, lo, mid), best(a, mid + 1, hi)
    s, cross_l = 0, float("-inf")
    for i in range(mid, lo - 1, -1):
        s += a[i]; cross_l = max(cross_l, s)
    s, cross_r = 0, float("-inf")
    for i in range(mid + 1, hi + 1):
        s += a[i]; cross_r = max(cross_r, s)
    return max(left, right, cross_l + cross_r)

T(n) = 2T(n/2) + n: two half-size calls plus a linear scan for the crossing sum. The recursion tree has log n levels doing n work each. It passes indices, so space is only the O(log n) call stack.

def msort(a):
    if len(a) <= 1: return a
    m = len(a) // 2
    L, R = msort(a[:m]), msort(a[m:])
    out, i, j = [], 0, 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]: out.append(L[i]); i += 1
        else: out.append(R[j]); j += 1
    return out + L[i:] + R[j:]

log n recursion depth × O(n) merge per level. Aux arrays = O(n).

import heapq
def top_k(nums, k):
    h = []
    for x in nums:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)
    return h

n pushes/pops on a heap. A tighter bound is O(n log k) since the heap stays at size <= k.

def qsort(a):
    if len(a) <= 1: return a
    p = a[len(a) // 2]
    lo = [x for x in a if x < p]
    mid = [x for x in a if x == p]
    hi = [x for x in a if x > p]
    return qsort(lo) + mid + qsort(hi)

Expected O(n log n) (average); worst-case O(n^2) with bad pivots. Treat the average case as the canonical answer.

def sum_matrix(grid):
    total = 0
    for row in grid:
        for x in row:
            total += x
    return total

Visit every cell of an n × m grid exactly once.

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[-1][-1]

Fill an m × n table once.

from functools import lru_cache
def lcs(a, b):
    @lru_cache(maxsize=None)
    def go(i, j):
        if i == len(a) or j == len(b): return 0
        if a[i] == b[j]: return 1 + go(i + 1, j + 1)
        return max(go(i + 1, j), go(i, j + 1))
    return go(0, 0)

n = len(a), m = len(b). Memoization solves each (i, j) pair once with O(1) work, and the worst case touches all of them. The cache holds n × m entries; the call stack adds O(n + m).

from collections import deque
def reachable(grid, sr, sc):
    rows, cols = len(grid), len(grid[0])
    seen = {(sr, sc)}
    q = deque([(sr, sc)])
    while q:
        r, c = q.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                    and grid[nr][nc] == 0 and (nr, nc) not in seen):
                seen.add((nr, nc)); q.append((nr, nc))
    return len(seen)

n rows by m columns. Each cell is enqueued at most once and checks 4 neighbors, so the work is O(n × m). The visited set and queue can hold every cell.

def has_pair_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return True
    return False

Classic nested loop over n × n/2 pairs.

void bubbleSort(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
            }
        }
    }
}

The inner bound shrinks each pass: (n-1) + (n-2) + ... + 1 = n(n-1)/2 comparisons. Halving the work keeps it quadratic. Swaps happen in place.

def build(strs):
    out = ""
    for s in strs:
        out += s
    return out

Python strings are immutable; each += copies the accumulated result. Use ''.join for O(n).

def sel_sort(a, start=0):
    if start >= len(a) - 1: return a
    m = start
    for i in range(start + 1, len(a)):
        if a[i] < a[m]: m = i
    a[start], a[m] = a[m], a[start]
    return sel_sort(a, start + 1)

T(n) = T(n-1) + n: each call scans the rest of the array, then recurses on one fewer element. n + (n-1) + ... + 1 = O(n^2). The call stack reaches depth n.

function unique(items) {
  const out = [];
  for (const x of items) {
    if (!out.includes(x)) out.push(x);
  }
  return out;
}

includes is a linear scan of out, which grows toward n, so the loop does up to n × n/2 comparisons. A Set makes the check O(1) and the whole function O(n).

def has_triple(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                if nums[i] + nums[j] + nums[k] == target:
                    return True
    return False

Three nested loops over n elements.

def fib(n):
    if n < 2: return n
    return fib(n - 1) + fib(n - 2)

Branching recursion with no memoization. Stack depth = n.

def count_subsets(nums, target):
    def go(i, total):
        if i == len(nums):
            return 1 if total == target else 0
        return go(i + 1, total + nums[i]) + go(i + 1, total)
    return go(0, 0)

Each element is either taken or skipped, giving 2^n leaves with O(1) work per call. Nothing is stored beyond the recursion, which is n deep.

def subsets(nums):
    out = [[]]
    for x in nums:
        out += [s + [x] for s in out]
    return out

There are 2^n subsets to generate. A tighter bound counts the total characters written, which is O(n * 2^n).

def derangements(arr):  # arr = list(range(n))
    n = len(arr)
    def go(k):
        if k == n: return 1
        count = 0
        for i in range(k, n):
            arr[k], arr[i] = arr[i], arr[k]
            if arr[k] != k:
                count += go(k + 1)
            arr[k], arr[i] = arr[i], arr[k]
        return count
    return go(0)

Swap-based backtracking explores permutations in place. The calls at depth k number at most n!/(n-k)!, which sums to about e × n!, and pruning only trims a constant fraction. Swaps undo themselves, so space is the O(n) stack.

def perms(arr):
    if not arr: return [[]]
    out = []
    for i, x in enumerate(arr):
        for p in perms(arr[:i] + arr[i+1:]):
            out.append([x] + p)
    return out

n! permutations, each of length n stored.