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 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 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.

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 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.

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.

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 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 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 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.