• Overview
• Details
• Exercises

Asymptotic notation provides a language to describe algorithm growth rates. Big-O gives upper bounds, Theta gives tight bounds, and Omega gives lower bounds.

• Big-O: upper bound (worst-case) up to constant factors
• Theta: tight bound (both upper and lower) up to constant factors
• Omega: lower bound (best-case) up to constant factors
• Little-o/ω: non-tight bounds (strictly smaller/greater growth)
• Common classes: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n)

1. Order these functions by growth: n log n, n^2, 2^n, log n, n.
2. Show that 3n + 7 is Θ(n) and 5n^2 + 4n is Θ(n^2).