Foundations
Big-Theta Notation (Tight Bound)
Difficulty: Intermediate
When you can say both that an algorithm runs in O(n log n) and that it must do at least Omega(n log n) work, the ceiling and floor have collapsed onto the same growth rate. That coincidence is the most informative complexity statement you...
Big-Theta Notation (Tight Bound)
When you can say both that an algorithm runs in O(n log n) and that it must do at least Omega(n log n) work, the ceiling and floor have collapsed onto the same growth rate. That coincidence is the most informative complexity statement you can make, and it is what Big-Theta Notation captures in a single symbol.
This lesson defines Theta(g(n)) as the intersection of Big-O and Big-Omega: there exist positive constants c1, c2, and n0 such that c1 * g(n) <= f(n) <= c2 * g(n) for all n >= n0, the so-called sandwich property. You will practice classifying functions and algorithms by their tight bound, learn when Big-Theta is appropriate (best and worst case have the same growth rate) versus when only Big-O is honest (the cases differ), and see why merge sort is Theta(n log n) while linear search is not Theta of any single function.
This lesson stitches together two ideas you have already met. From Big-O Notation (Upper Bound) you have the ceiling f(n) <= c * g(n), and from Big-Omega Notation (Lower Bound) you have the floor f(n) >= c * g(n). Big-Theta simply requires both bounds to hold for the same g(n), so an algorithm only earns a Theta label when its upper and lower bounds genuinely match.
With all three asymptotic notations in hand, you will be ready to switch focus to Memory Models, where the same growth-rate thinking gets applied to space rather than time.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Define Big-Theta as the intersection of Big-O and Big-Omega (tight bound).
Apply the formal definition of Big-Theta to verify tight bounds.
Determine the Big-Theta of common algorithms and code patterns.
Explain when Big-Theta is more informative than Big-O alone.
Choose the appropriate notation (O, Omega, Theta) for different contexts.
Why This Matters
01
Big-Theta is the most precise asymptotic statement you can make about an algorithm's growth rate.
02
When you say an algorithm is Theta(n log n), you communicate both the ceiling and the floor in one expression.
03
Understanding Big-Theta helps you identify truly optimal algorithms and avoid imprecise complexity claims.
Key Terms
6 terms you'll encounter in this lesson
Big-Theta (Theta)
A notation that describes a tight bound on growth rate. f(n) = Theta(g(n)) means f grows at the same rate as g, up to constant factors.
Tight bound
When the upper bound (Big-O) and lower bound (Big-Omega) are the same function, giving the exact growth rate.
Sandwich property
Big-Theta 'sandwiches' the function between two constant multiples: c1 * g(n) <= f(n) <= c2 * g(n).
Asymptotically tight
An algorithm whose best and worst cases have the same Big-O/Big-Omega is asymptotically tight.
Dominant term
The fastest-growing term in an expression. The dominant term determines the Big-Theta class.
Growth rate
How fast a function increases as input size grows. Big-Theta precisely characterizes this rate.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"Big-Theta means the algorithm always takes the same time"
Big-Theta describes the growth rate, not the exact time. Theta(n^2) means the work grows as n^2, but two different inputs of the same size n may still take different amounts of time. Theta applies when the best and worst cases have the same growth rate.
"Every algorithm has a Big-Theta"
Not always. If an algorithm's best case is O(n) but worst case is O(n^2), there is no single Big-Theta for 'the algorithm' across all cases. You can state Theta for a specific case though: 'worst case is Theta(n^2)'.
"Big-Theta and Big-O mean the same thing"
Big-O is an upper bound only. Big-Theta is both upper and lower bound. Saying f(n) = O(n^2) allows f to be linear, but f(n) = Theta(n^2) guarantees f is exactly quadratic growth.
"I should always use Big-Theta instead of Big-O"
In practice, Big-O is more commonly used because (1) we often care most about worst-case upper bounds, and (2) tight bounds are harder to prove. Use Theta when you can prove it; use O when you only know the upper bound.