Big-Theta Examples and Common Functions
You'll learn: How to identify tight Big-Theta bounds for real expressions and recognize common algorithm complexity classes.
The Core Idea
Now that you understand Big-Theta's formal definition, let's apply it to actual functions you'll encounter. The key skill is finding the dominant term — the part that grows fastest as input size increases — because that's your tight bound.
Walking Through an Example
Consider the function f(n) = 3n² + 5n + 2.
As n gets large:
- The 3n² term dominates everything else
- The 5n grows much slower than n²
- The constant 2 barely matters at all
Therefore: 3n² + 5n + 2 = Θ(n²)
We drop the coefficients (the 3) and the lower-order terms (5n + 2) because they don't affect the growth rate. Think of it like measuring a skyscraper — you care about its height in stories, not whether each floor is 10 feet or 10 feet 3 inches tall.
Common Big-Theta Classifications
When you analyze algorithms, you'll frequently see these tight bounds:
- Θ(1): Array indexing, simple arithmetic
- Θ(log n): Binary search on sorted data
- Θ(n): Single loop through an array, linear search
- Θ(n log n): Efficient sorting algorithms (future topic)
- Θ(n²): Nested loops over the same array
For example, a function with 7n + 12 = Θ(n), and 4n² - 100n + 50 = Θ(n²).
The Pattern
Always look for the highest-degree term, drop coefficients, and that's your Θ classification. It's not just upper or lower bound — it's the exact growth rate.
Key Takeaway: Big-Theta captures the precise growth rate by identifying the dominant term; expressions like 3n² + 5n + 2 simplify to Θ(n²) because n² is the fastest-growing component.