Big O notation · part 7 of 8
What Θ, Ω, and O really mean
You don't need to read this page, but you probably will because you're an autodidactic son of a gun!
The formalism
The formal definition looks scarier than it is, so start with the picture: past a certain size, your function's cost stays under a fixed multiple of its shape. Take 3n + 10. It's O(n) because once n reaches 10, it never rises above 4n. The multiple is 4, the size you start checking from is 10.
The notation just puts letters on those two numbers. Call f(n) the real cost and g(n) the shape: f is O(g) when some multiplier c (our 4) and some starting size n₀ (our 10) keep f(n) at or below c · g(n) for every n past n₀. The c lets you ignore constant factors; the n₀ lets you ignore the mess while n is small. The same move from the recipe, just wearing a tie.
Have a play below. Drag c and n₀, and switch the shape g. Watch how raising c or pushing n₀ to the right lets the bound clear 3n + 10, how n² swallows it with room to spare, and how a flat 1 never can: that last one is what "not O(1)" looks like.
✓ For every n past n₀ = 10, 3n + 10 stays at or below 4 × n. So 3n + 10 is O(n).
f(n): your code, 3n + 10g(n): the shape, nc·g(n): the limit, 4 × n
The other letters
Big O is strictly an upper bound: f is O(g) means f grows no faster than g. There are siblings. Ω (omega) is the lower bound, f grows no slower than g. Θ (theta) is both at once, a tight bound, f grows exactly like g. When people say "the running time is O(n²)" they very often mean Θ(n²), they're just being loose with the letter.