COMP90038 · Algorithms And Complexity
Foundations: the Cost Model and Asymptotics
Every later technique is judged against the toolkit built here. COMP90038 starts with a cost model — the Word-RAM, where a fixed set of operations (arithmetic, comparison, array indexing, assignment) each cost O(1) — so “running time” means counting basic operations as a function of input size n, not wall-clock seconds. On top of that sit the asymptotic notations: O (upper bound), Ω (lower bound) and Θ (tight bound), which describe growth as n → ∞ while discarding constants and lower-order terms. The chapter then insists you always say which case you are bounding — worst, expected (average over random inputs) or amortised (averaged over a worst-case sequence) — because conflating them is the classic analysis error. Finally it sets up recurrences (how a recursive algorithm's cost refers to itself) and primes the Master-Theorem ritual that the divide-and-conquer chapter cashes in. Get this language exact and the rest of the subject becomes a matter of plugging each algorithm into it.
What this chapter covers
- 01The Word-RAM cost model and the basic O(1) operations
- 02Big-O, Ω and Θ — upper, lower and tight asymptotic bounds
- 03Worst-case vs expected vs amortised — always state which
- 04Common growth-rate hierarchy: 1 < log n < n < n log n < n² < 2ⁿ
- 05Setting up recurrences from recursive code; priming the Master Theorem
Worked example: bounding a nested loop and naming the case
for i in 1..n: for j in i..n: x += 1. Then state whether your bound is worst-, expected- or amortised-case.- +2Count the inner runs. For each i the inner loop runs (n − i + 1) times, so the total is ∑i=1..n(n − i + 1) = n + (n−1) + … + 1 = n(n+1)/2.
- +1Drop constants and lower terms. n(n+1)/2 = ½n² + ½n, whose dominant term is n², so the count is Θ(n²) — tight, since the sum is both O(n²) and Ω(n²).
- +1Name the case. The loop bounds do not depend on the data, so worst, expected and best all coincide — this is a worst-case (and in fact exact) Θ(n²).
Key terms
- Word-RAM model
- The standard cost model for algorithm analysis: memory is an array of fixed-width words, and a fixed set of operations — arithmetic, comparison, array indexing, assignment, control flow — each cost O(1). Running time is the count of these basic operations as a function of input size.
- Big-O notation
- An asymptotic upper bound: f(n) = O(g(n)) means f grows no faster than g, i.e. f(n) ≤ c·g(n) for some constant c and all large n. It hides constants and lower-order terms, so it describes the shape of growth, not an exact count.
- Tight bound (Θ)
- f(n) = Θ(g(n)) means g is both an upper and a lower bound — f grows exactly like g up to constants. It is the strongest of the three notations and the one exam answers should give whenever the growth is pinned down.
- Amortised cost
- The average cost per operation over a worst-case sequence of operations. It smooths out occasional expensive steps (like a dynamic-array resize) against the many cheap ones, giving a per-operation figure that is honest about a sequence even when one step is costly.
- Recurrence
- An equation that expresses an algorithm's running time in terms of its time on smaller inputs, e.g. T(n) = 2T(n/2) + n. Solving it — by the Master Theorem or a recurrence tree — yields the closed-form asymptotic bound.
Foundations: the Cost Model and Asymptotics FAQ
Why count operations instead of timing the code?
Because wall-clock time depends on the machine, the language and the compiler, none of which are intrinsic to the algorithm. Counting basic operations as a function of n gives a hardware-independent measure that predicts how the cost scales — which is what the exam and real engineering decisions care about.
What is the difference between O, Ω and Θ?
O is an upper bound (no faster than), Ω a lower bound (no slower than), and Θ both at once (exactly this growth). Saying an algorithm is O(n²) does not forbid it from being faster; Θ(n²) pins it down. In True/False exam questions, distinguishing these precisely is often the whole mark.
When do worst, expected and amortised differ?
When the cost depends on the input or the operation sequence. Quicksort is Θ(n log n) expected but Θ(n²) worst-case; a dynamic-array append is O(n) worst-case on a resize but O(1) amortised. If the loop bounds are data-independent, all three coincide — always say which one you mean.
Exam move
Make the asymptotic vocabulary reflexive, because Q2 of the exam (True/False with justification) lives here: to prove an O-claim, exhibit the constant c; to disprove an “always/never” claim, give a counterexample. Practise turning code into a recurrence and a sum, then collapsing it to a Θ bound by dropping constants and lower-order terms. Above all, always state which case you are bounding — worst, expected or amortised — because an unqualified bound is the most common way to lose an otherwise-correct mark.
