1.1 What exactly are we measuring?

For an algorithm A and input of size n (bits, array length, number of vertices — state your convention!):

• Time complexity T(n): the maximum number of basic steps A performs on any input of size n — the worst case, expressed as a function of n.
• Space complexity S(n): the maximum number of memory cells A uses beyond the input.

We measure growth rates, not stopwatch seconds: hardware changes constants, but the growth rate is a property of the algorithm itself.

1.2 Big-O and its siblings — the formal definitions

Worked proof (exam staple). Show 3n² + 10n + 5 = O(n²): For n ≥ 1, 3n² + 10n + 5 ≤ 3n² + 10n² + 5n² = 18n². Take c = 18, n₀ = 1. ∎

Useful manipulation rules: drop constants and lower-order terms; O(f) + O(g) = O(max(f,g)); O(f)·O(g) = O(f·g); logarithm bases don't matter (log₂n = Θ(log₁₀n)).

1.3 The growth-rate ladder

O(1) ⊂ O(log n) ⊂ O(√n) ⊂ O(n) ⊂ O(n log n) ⊂ O(n²) ⊂ O(n³) ⊂ O(2ⁿ) ⊂ O(n!)
└──────────────── polynomial: "tractable" ────────────────┘ └─ exponential: "intractable" ─┘

Why the polynomial/exponential split is the dividing line — let one step take 1 µs and watch n grow:

Doubling CPU speed adds +1 to the n an exponential algorithm can handle. No hardware will ever rescue 2ⁿ — that is the Cobham–Edmonds thesis: tractable = polynomial time.

1.4 Space complexity and its relationship to time

• Space can be reused; time cannot. That asymmetry makes space classes behave differently.
• A machine running in time T(n) can touch at most T(n) cells: TIME(f) ⊆ SPACE(f).
• A machine using space S(n) ≥ log n has at most 2^O(S(n)) distinct configurations, so it either halts within that bound or loops forever: SPACE(f) ⊆ TIME(2^O(f)).

Important space classes to recognise now (Unit 4 returns to them): L = O(log n) space, PSPACE = polynomial space.

1.5 Decision problems and languages

Complexity theory standardises everything as decision problems — questions with YES/NO answers — encoded as languages:

L = { x ∈ {0,1}* : the answer for instance x is YES }

"Solve the problem" = "decide membership in L". Examples:

• PRIME = { ⟨n⟩ : n is prime }
• HAMPATH = { ⟨G⟩ : graph G has a Hamiltonian path }

Optimisation problems convert to decision versions by adding a threshold k ("is there a tour of cost ≤ k?") — and the decision version is easier-or-equal, so hardness of the decision version implies hardness of optimisation.

1.6 Worst, best, average — and why worst case rules

Complexity theory is built on the worst case because guarantees must hold for every input — an adversary picks the input, you pick the algorithm.

1.7 Deriving Big-O from code — three worked patterns

Pattern 1 — nested loops: count iterations.

for i = 1 to n:
    for j = 1 to i:
        O(1) work

The inner body runs 1 + 2 + ... + n = n(n+1)/2 times → Θ(n²). Rule: sum the iteration counts exactly, then keep the dominant term.

Pattern 2 — the halving loop.

i = n
while i > 1:   i = i / 2

After k passes i = n/2ᵏ; the loop stops when n/2ᵏ ≤ 1, i.e. k ≥ log₂ n → Θ(log n). Any loop whose control variable is multiplied or divided by a constant each pass is logarithmic.

Pattern 3 — recursion via recurrences. Binary search satisfies T(n) = T(n/2) + O(1) → O(log n). Merge sort satisfies T(n) = 2T(n/2) + O(n): unrolling gives log n levels, each costing O(n) in total → O(n log n).

Master theorem (state it for recurrence questions). For T(n) = a·T(n/b) + f(n) with a ≥ 1, b > 1, let c = log a / log b (so nᶜ counts the leaves of the recursion tree):

Check on merge sort: a = 2, b = 2 → c = 1, f(n) = n = Θ(n¹) → case 2 → Θ(n log n) ✓.

1.8 Comparing growth rates by limits (a fast exam tool)

Evaluate lim f(n)/g(n) as n → ∞:

Example: is n log n = O(n^1.5)? lim (n log n)/n^1.5 = lim (log n)/√n = 0 → yes, and strictly. Standard facts to quote: log n grows slower than every nᵉ (ε > 0); every polynomial nᵏ grows slower than every exponential cⁿ (c > 1); every cⁿ grows slower than n!.

1.9 A worked Ω and Θ proof

Show n²/2 − 3n = Θ(n²). Upper bound: n²/2 − 3n ≤ n² for all n ≥ 1 (take c₂ = 1). Lower bound: n²/2 − 3n ≥ n²/4 ⟺ n²/4 ≥ 3n ⟺ n ≥ 12 (take c₁ = 1/4, n₀ = 12). Both directions exhibited with explicit constants — exactly the presentation the exam wants. ∎

Exam pointer

• "Prove from the definition that f = O(g)" (4–5 marks): produce explicit c and n₀, verify the inequality line by line, finish with ∎. Limits are not allowed if the question says from the definition.
• "Arrange functions in increasing order of growth" (4 marks): a typical set is 1, log n, √n, n, n log n, n², 2ⁿ, n!; justify one or two adjacent pairs with the limit test.
• "Distinguish time vs space complexity / worst vs average case" (short note): reproduce the tables of §1.4 and §1.6.

Self-check

1. Give explicit c and n₀ proving 5n³ + 2n = O(n³).
2. Why does the base of a logarithm not matter inside O(·)?
3. State the two containments connecting TIME and SPACE and give the one-line reason for each.
4. Convert the optimisation problem "find the largest clique in G" into a decision problem.
5. True or false: f = O(g) and f = Ω(g) together imply f = Θ(g)? (True — that is the definition of Θ.)