Lecture 4 - Asymptotic Notation and Growth Rates
(Skeleton for Fall 2026.)
Big-O, Carefully
TODO: the definition, stated wordily and precisely: f(n) is O(g(n)) means there exist a constant c greater than 0 and a threshold n₀ such that for every n at least n₀, f(n) is at most c times g(n). Unpack the quantifiers; why c absorbs constant factors and n₀ absorbs small-input noise; prove 3n² + 50 is O(n²) straight from the definition.
Ω, Θ, and Little-o
TODO: lower bounds, tight bounds; proving a function is NOT O(g) by negating the quantifiers (good quantifier practice from Lecture 1).
Growth Rate Zoo
TODO: log, polynomial, exponential; why polynomial versus exponential is THE dividing line the whole complexity unit is built on.
Why Worst Case, and the Idea of a Complexity Class
TODO: worst-case as a guarantee over all inputs; a complexity class as "the set of problems solvable within a resource budget"; preview of P as the first class we will define precisely in Lecture 13.
Exercises
These are not collected or graded; they are your study material, and the exams will look like them. In every exercise, start by restating the definition you are using in full.
Big-O witnesses
Generate as many fresh instances as you like; each one comes with a hidden solution, and the checker accepts any valid constants, not just the reference ones. Work each instance on paper the way you would on an exam, then check.