title: "Big-Theta"

Big-Theta

Definition. $f(n) = \Theta(g(n))$ means $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$ both hold: the two functions have the same growth rate up to constant factors.

A Θ proof has two halves, one witness pair per direction (Lecture 9, Example 4). See Big-O and Big-Omega.