Time & Space Complexity

Big O gives an asymptotic upper bound on how a cost function grows with input size, discarding constants and lower-order terms. It compares algorithms independently of hardware; constants still matter in practice at small n..

def chef_a(guests):  return 3 * guests        # O(n)
def chef_b(guests):  return 10 * guests       # O(n)
def chef_c(guests):  return guests ** 2 // 2  # O(n^2)

chef_c(4)   # 8   — cheapest here
chef_c(300) # 45000 — and never cheapest again

O(1) means the operation cost is bounded by a constant regardless of n: array indexing, hash lookup, stack push. It may still be slow in absolute terms — constant does not mean fast, it means unaffected by size..

def toggle(lights):
    lights.on = not lights.on     # one operation

# n = 4 bulbs      -> 1 operation
# n = 1_000_000    -> 1 operation

d = {"k": 1}
d["k"]        # O(1)
a[i]          # O(1)
stack.append(x)  # amortised O(1)

O(n) means cost grows in direct proportion to input size — a single pass such as summing, searching unsorted data, or copying. It is optimal for any problem that must inspect every element at least once..

def greet_all(guests):
    for g in guests:
        shake(g)          # exactly n handshakes

# 8 guests  -> 8
# 16 guests -> 16    (doubles with n)
sum(values)       # O(n)
max(values)       # O(n)
x in a_list       # O(n)

O(n²) arises from nested iteration over the input — bubble sort, naive pair comparison, adjacency-matrix scans. Growth is quadratic: 10× the input is 100× the work, which usually makes it unusable past a few thousand elements..

def everyone_greets_everyone(guests):
    for a in guests:
        for b in guests:
            if a is not b:
                shake(a, b)     # n^2 handshakes

# 10 guests  ->    90
# 100 guests -> 9_900   (100x, not 10x)

O(log n) arises when each step discards a constant fraction of the remaining input: binary search, balanced tree operations, heap sift. Doubling n adds one operation, so it is effectively flat at any realistic scale..

def find_page(pages, name):
    lo, hi = 0, len(pages) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if pages[mid] == name:
            return mid
        if pages[mid] < name:
            lo = mid + 1
        else:
            hi = mid - 1

# 1_000_000 names -> about 20 tears

O(n log n) is the lower bound for comparison-based sorting and the complexity of merge sort, heapsort and practical quicksort. It sits close enough to linear that it is rarely the bottleneck..

import math

n = 8
math.log2(n)        # 3 levels of splitting
n * math.log2(n)    # 24 units of work

sorted(a)           # Timsort: O(n log n)
heapq.heapify(a)    # O(n), then log n per pop

Asymptotic differences are invisible at small n and dominant at large n. Choose by the growth class for the expected scale, then optimise constants; profile before assuming the asymptotically better algorithm wins at your actual input size..

import math

for n in (10, 100, 1000):
    print(n,
          1,                      # O(1)
          round(math.log2(n)),    # O(log n)
          n,                      # O(n)
          round(n * math.log2(n)),# O(n log n)
          n * n)                  # O(n^2)

Space complexity counts auxiliary memory as a function of n, excluding the input. Merge sort needs O(n) auxiliary; quicksort O(log n) stack; in-place algorithms O(1).

# auxiliary space, excluding the input
bubble_sort(a)    # O(1)      swaps in place
quick_sort(a)     # O(log n)  call stack
merge_sort(a)     # O(n)      scratch lists

sum(x for x in a)      # O(1)  generator
sum([x for x in a])    # O(n)  builds a list

Amortised analysis averages the cost of an operation over a worst-case sequence. Dynamic array append is amortised O(1) despite O(n) resizes because doubling makes resizes exponentially rare.

a = []
for i in range(24):
    a.append(i)      # usually 1 write
                     # occasionally copies everything

import sys
sys.getsizeof(a)     # jumps at each resize
# amortised O(1) per append

Selection is a fit between access pattern and structure: hash map for keyed lookup, dynamic array for indexed iteration and cache locality, balanced tree for ordered queries, heap for repeated extreme extraction, adjacency list for sparse graphs. Decide by the dominant operation and expected n..

# pick by the operation you do MOST
users[user_id]              # dict  -> O(1)
for row in rows:            # list  -> O(1) index
heapq.heappop(tasks)        # heap  -> O(1) min
bisect.insort(scores, s)    # sorted list -> order
deque.popleft()             # queue -> O(1) both ends