Asymptotic Notation Made Precise
The definition behind big-O: f(n) is O(g(n)) when some constant multiple of g stays above f from some input size onward. Big-Omega bounds from below and big-Theta bounds from both sides, so a claim about growth becomes something a student can argue for rather than assert.
What a learner can do afterwards
- Name a constant and a starting size that make a given big-O claim true
- Say what big-Omega and big-Theta each add to a big-O statement
- Explain why an O(n squared) method can still beat an O(n) one on small inputs
1 · Read
Big-O is a promise about the long run. Saying a running time is O of g means some constant multiple of g never drops below it once inputs are big enough. It is an upper bound from some starting size onward, not an exact prediction for every input.
Take 5 n squared plus 30 n. Six copies of n squared stay above it from n equal to 30 onward, because the extra 30 n fits inside one n squared once n reaches 30. So the constant 6 with starting size 30 makes the O of n squared claim true. The same function is not O of n, since the n squared term outgrows every constant multiple of n.
Big-Omega bounds from below: the running time stays above some constant multiple, so it certifies a minimum. Big-Theta does both at once, sandwiching the running time between two multiples. Binary search is honestly O of log n, not Theta of log n, because a lucky first guess finishes in constant time. A minimum grabbed from index 0 of a sorted list takes the same single step always, so it is Theta of 1.
An O of n squared method with tiny constants can beat an O of n method with huge ones while n is small. Only past the crossover point does slower growth always win. So claim O when you hold an upper bound, and save Theta for when you can justify the lower bound too.
Use O for an upper bound, Omega for a lower bound, and Theta only when you can sandwich both sides.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.