title: "Big-Omega"

Big-Omega

Definition. $f(n) = \Omega(g(n))$ means there exist a constant $c > 0$ and a threshold $n_0$ such that for every $n \geq n_0$, $f(n) \geq c \cdot g(n)$: eventual domination from below.

It is Big-O with the inequality reversed; holding in both directions at once is Big-Theta. Defined in Lecture 9.