Exit
Lesson 086 · Step 1 of 4Streak 00

Beyond upper bounds

Definition 12

Omega and Theta

f(n)=Ω(g(n))f(n) = Ω(g(n)) means f(n)≥c⋅g(n)f(n) \ge c\cdot g(n) for all large nn, for some c>0c > 0. f(n)=Θ(g(n))f(n) = Θ(g(n)) means both O(g)O(g) and Ω(g)Ω(g) hold.

Big-O is an upper bound, Ω is a lower bound, and Θ says the growth rate is exactly that.