Course contentsShow
← Computer Science
Lesson 295 of 2,8727. Introduction to Complexity AnalysisFree lesson

Big-Theta Examples and Common Functions

Working through examples like 3n² + 5n + 2 = Θ(n²) and identifying tight bounds for common algorithms.

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.