O ≤ · Ω ≥ · Θ = (tight). Drop constants + lower terms.
Lookup: naive unsorted O(n) · binary (sorted!) O(log n) · balanced BST O(log n) · hash exp O(1) / worst O(n) (all keys collide) · Bloom O(k)=O(1), FP yes / FN no.
No RAM: disk I/O dominates → B-tree / Bloom prefilter.
Loops: nested independent = multiply; Σ1..n = n(n+1)/2 = Θ(n²); halving loop = Θ(log n). Space: recursion depth = stack: bin-search rec O(log n), iter O(1).
| rec | a,b,d | → |
|---|---|---|
| binary search | 1,2,0 | log n |
| merge sort (k-way too) | 2,2,1 | n log n |
3-branch naive rec (deg): T ≤ 3T(n−1)+O(1) → O(3ⁿ); k-branch → O(kⁿ). deg: 1,1,1,3,5,9,17…
Unequal split sizes ⇒ Master NOT applicable — say it, then → ★§3.
Ex: T=T(n/2)+T(n/3)+T(n/6)+n: ½+⅓+⅙=1 → p=1; d=1=p → Θ(n log n).
Ex: T=3T(n/2)+4T(n/4)+n²: ¾+4/16=1 → p=2; d=2=p → Θ(n² log n).
MoM ref: T=T(n/5)+T(7n/10)+O(n): p≈0.84<1=d → Θ(n).
Answer order: (1) “Master N/A — unequal splits” (2) Σaᵢ(1/bᵢ)ᵖ=1 with the integer test shown (3) d vs p (4) boxed Θ. If p not integer: bracket on calculator like binary search (won't happen per prof).
| best | avg | worst | spc | st? | ip? | |
|---|---|---|---|---|---|---|
| bubble | n²* | n² | n² | 1 | Y | Y |
| selection | n² | n² | n² | 1 | N | Y |
| insertion | n | n² | n² | 1 | Y | Y |
| merge | n lg n | n lg n | n lg n | n | Y | N |
| quick | n lg n | n lg n | n² | lg n | N | Y |
| heap | n lg n | n lg n | n lg n | 1 | N | Y |
*bubble + swapped-flag → best O(n). quick worst: sorted/equal + bad pivot; fix: random / median-of-3. stable = equal keys keep order.
Bound: comparison ≥ log₂(n!) = Ω(n log n) (decision tree). Beat: counting/bucket O(n+k), radix O(dn) — bounded keys.
def merge(S1, S2, S):
i = j = 0
while i + j < len(S):
if j == len(S2) or \
(i < len(S1) and S1[i] < S2[j]):
S[i+j] = S1[i]; i += 1
else:
S[i+j] = S2[j]; j += 1
merge sort: n<2 return · split · recurse · merge. k-way: T=kT(n/k)+O(n) → same n log n.
★ BogoSort: shuffle, check sorted O(n), repeat. Best O(n), expected O(n·n!), worst ∞. Quantum Bogo: superpose all n! perms, measure; sorted branch → done in O(n) (joke: destroy unsorted universes). Not real: measurement collapses to ONE random perm — parody, unlike Grover's genuine O(√n).
def f(n, memo=None): # top-down DP
if memo is None: memo = {}
if n < 3: return 1 # base
if n not in memo:
memo[n] = (f(n-1,memo)+f(n-2,memo)
+f(n-3,memo))
return memo[n] # O(n) time
from functools import lru_cache · @lru_cache(maxsize=None) on naive rec. Bottom-up: rolling vars a,b,c=b,c,a+b+c → O(1) space.
def binary_search(data, t): # iter
lo, hi = 0, len(data)-1
while lo <= hi:
mid = (lo+hi)//2
if data[mid]==t: return True
if data[mid]<t: lo = mid+1
else: hi = mid-1
return False
def bisection(f,a,b,tol,max_it):
if sign(f(a))==sign(f(b)):
raise ValueError # need sign change
for _ in range(max_it):
m = (a+b)/2
if abs(f(m)) < tol:
return m # tol: |f(m)|<tol
if sign(f(m))==sign(f(a)): a = m
else: b = m
return (a+b)/2
sign: −1/0/1 if-chain. Invariant: sign(f(a))≠sign(f(b)) (IVT). min/max rec: base=last elem; combine min/max(cur, rest).
linked: O(1) head ins/del, no resize · array: O(1) index, cache-local, append O(1) amortized (doubling).
insert after cur: node.next = cur.next
cur.next = node # order!
remove_first: if head:
head = head.next; size -= 1
def __iter__(self): # generator
cur = self._head
while cur is not None:
yield cur._element
cur = cur._next_element
walk k hops → (k+1)-th node · middle: size//2−1 hops → node before middle · odd size → raise ValueError · always ±size · empty case first!
MyArray.insert: neg k → k+=n · clamp · full → _resize(2·cap) · shift n→k backwards · A[k]=v · n+=1. __setitem__: neg fix + bounds only.
Dunders: obj[k]=v→__setitem__ · obj[k]→__getitem__ · len→__len__ · for→__iter__. Queue: FIFO · circular: front idx + mod. Stack: LIFO.
G=(V,E); weighted digraph G=(V,E,w), w:E→ℝ, E ordered pairs, A asymmetric. Declare “row = from”. 0 = no edge. List V and E explicitly, then the matrix.
adj-matrix O(V²), edge test O(1) · adj-list O(V+E). Frontier = discovered, not yet expanded. list.pop(0) Θ(n) → deque.popleft() O(1). BFS queue · DFS stack · Dijkstra min-heap O((V+E)log V).
def is_symmetric(node): # whole thing!
if node is None: return True
return mirror(node.left, node.right)
def mirror(l, r):
if l is None and r is None: return True
if l is None or r is None: return False
return mirror(l.left, r.right) and \
mirror(l.right, r.left)
symmetric = equal to its inverse · STRUCTURE only, ignore values · single child breaks symmetry unless mirrored. Tree sum/height: val + recurse children, guard None. Traversals: pre NLR / in LNR / post LRN.
Hash table task: given h(i) + keys → compute h per key (show the line), draw table, chaining: list per bucket in insertion order. Load α=m/n → exp O(1+α). No code needed.
def __setitem__(self, k, v): # obj[k]=v
for item in self._table:
if k == item._key:
item._value = v; return
self._table.append(self._Item(k, v))
Theory (know, not quizzed): P(bit=0)=(1−1/n)^{km}≈e^{−km/n} ((1−1/n)ⁿ≈1/e) · ε=(1−e^{−km/n})^k · k*=(n/m)ln2 → integer, test neighbors. Ex: m=5,n=24: k=3, ε≈0.10 · m=20,n=100,k=3: P(0)=e^{−0.6}≈.549, ε≈.092.
Nested dict: defaultdict(dict) or create inner {} first.
|a⟩ = α|0⟩+β|1⟩ · α,β ∈ ℂ amplitudes · P(0)=|α|², P(1)=|β|² · |α|²+|β|²=1 · superposition until measured (bit: 0 or 1). X=[0 1;1 0] swaps α,β · H=1/√2[1 1;1 −1] → equal superposition.
Grover: unstructured search O(√n) vs O(n), quadratic. Shor: factoring, poly O((log N)³), exponential, breaks RSA. This year: quantum = the BogoSort task (§4) + maybe qubit def.
◇ Strassen — NOT in this year's exam. Safety line: naive matmul O(n³) (n² entries × n); Strassen 7 mults: T=7T(n/2)+O(n²) → Master a=7,b=2,d=2: log₂7≈2.807>2 → O(n^2.807). M's are given if ever asked; check C_ij = substitute, expand, cancel.
◇ Median-of-medians — nothing specific, no code. Groups of 5 → median of medians as pivot → T(n)=T(n/5)+T(7n/10)+O(n) → Θ(n) (the A–B reference).
Strategy: ID3 problem = 15/20-to-pass → pick it. ~38 min/problem. Stuck? leave the setup — method earns partial credit. Support everything.