Asymptotic Notation

A motivating example

Consider two algorithms for the same problem:

• Algorithm A takes 2n + 100 operations

• Algorithm B takes n² + 5 operations

For small inputs, Algorithm B might actually be faster because 100 is a larger constant than 5:

At n = 5, Algorithm B is nearly 4x faster. At n = 1,000, Algorithm A is nearly 500x faster. At n = 10,000, Algorithm A is nearly 5,000x faster.

Asymptotic notation captures this essential truth: Algorithm A grows linearly while Algorithm B grows quadratically. We write that A is O(n) and B is O(n²), ignoring the constants and lower-order terms that matter less at scale.

What "asymptotic" means

The term "asymptotic" comes from mathematics, referring to behavior as a variable approaches a limit—in this case, as input size n approaches infinity.

An asymptote is a line that a curve approaches but never quite reaches. When we analyze algorithms asymptotically, we focus on the curve's shape at large values, not its exact position.

This matters because:

• Real-world data often grows. Today's 1,000 users become tomorrow's 1,000,000.

• Growth rate determines feasibility. A quadratic algorithm on a million items requires a trillion operations.

• Hardware improvements cannot overcome fundamental scaling. Faster computers shrink constants but do not change growth curves.

Big-O: Upper bound

Big-O notation (written O(...)) describes an upper bound on growth rate. When we say an algorithm is O(n²), we mean:

"As input size grows, the running time grows at most proportionally to n²."

Key points about Big-O:

• It provides a guarantee: the algorithm will not be worse than this.

• It is an upper bound, so it may not be tight.

• An O(n) algorithm is also technically O(n²), O(n³), etc. (the bound is not violated, just loose).

• In practice, we try to give the tightest O bound we can prove.

Big-O answers the question: "How bad can this algorithm get?"

Big-Omega: Lower bound

Big-Omega notation (written Ω(...)) describes a lower bound on growth rate. When we say an algorithm is Ω(n), we mean:

"As input size grows, the running time grows at least proportionally to n."

Key points about Big-Omega:

• It provides a floor: the algorithm will take at least this much work.

• It is a lower bound, so the algorithm might be slower.

• An Ω(n²) algorithm is also Ω(n), Ω(log n), etc. (weaker lower bounds hold).

• Lower bounds are harder to prove because you must show no faster approach exists.

Big-Omega answers the question: "How good can this algorithm possibly be?"

Big-Theta: Tight bound

Big-Theta notation (written Θ(...)) describes a tight bound. When we say an algorithm is Θ(n log n), we mean:

"As input size grows, the running time grows exactly proportionally to n log n—no faster, no slower."

Key points about Big-Theta:

• It is the most precise characterization.

• An algorithm is Θ(f(n)) if and only if it is both O(f(n)) and Ω(f(n)).

• Tight bounds are the goal of analysis when achievable.

• Not all algorithms have known tight bounds.

Big-Theta answers the question: "Exactly how does this algorithm scale?"

A height analogy

Think of it like describing a person's height:

• O(6 feet) means "at most 6 feet tall"

• Ω(5 feet) means "at least 5 feet tall"

• Θ(5'8") means "exactly 5'8" (within reasonable precision)

If someone is exactly 5'8":

• Saying they are O(6 feet) is true but imprecise

• Saying they are Ω(5 feet) is true but imprecise

• Saying they are Θ(5'8") is true and precise

The goal is always to give the tightest bounds possible.

Relationships in set terms

Mathematically, these notations define sets of functions:

• O(f(n)) is the set of functions that grow no faster than f(n)

• Ω(f(n)) is the set of functions that grow no slower than f(n)

• Θ(f(n)) is the intersection: functions that grow at exactly the rate of f(n)

When we write "algorithm A is O(n²)," we mean the algorithm's running time function belongs to the set O(n²).

When to use Big-O

Big-O is the most common notation in everyday software engineering. Use it when:

Discussing worst-case performance: Most engineers care about guarantees. Knowing an algorithm is O(n log n) means it will not suddenly become unusably slow.

Communicating with colleagues: Big-O is industry standard. Saying "this is O(n)" conveys meaning instantly to other engineers.

Upper bound is sufficient: Often you just need to know the algorithm will not exceed a certain cost, even if it might be faster.

Lower bound is unknown: If you cannot prove a lower bound, Big-O is all you have.

When to use Big-Omega

Big-Omega appears most often in theoretical computer science. Use it when:

Proving problem lower bounds: To show that no algorithm can solve a problem faster than some rate, you prove a lower bound on the problem itself.

Demonstrating optimality: If you have an O(f(n)) algorithm and can prove the problem requires Ω(f(n)) work, your algorithm is optimal.

Analyzing best-case scenarios: Sometimes you want to know the minimum work an algorithm must do.

When to use Big-Theta

Big-Theta gives the most information. Use it when:

Both bounds are known: If you can prove matching upper and lower bounds, Θ is the right notation.

Analyzing well-understood algorithms: Classic algorithms like merge sort (Θ(n log n)) have known tight bounds.

Maximum precision is needed: When comparing algorithms with similar complexity, tight bounds matter.

Ignoring constant factors

In asymptotic notation:

• O(2n) = O(n)

• O(100n) = O(n)

• O(0.001n) = O(n)

All linear functions are equivalent in Big-O terms.

Why ignore constants?

Constants depend on implementation. The same algorithm might be 10x faster in C than in Python, but both have the same growth rate. The constant reflects the language, not the algorithm.

Constants depend on hardware. A faster CPU shrinks all constants equally. This does not change which algorithm scales better.

Constants become irrelevant at scale. Whether you do 2n or 100n operations, both are dwarfed by n² once n is large enough.

Ignoring lower-order terms

In asymptotic notation:

• O(n² + n) = O(n²)

• O(n² + 1000n + 5000) = O(n²)

• O(n³ + n² + n + 1) = O(n³)

Only the fastest-growing term matters.

Why ignore lower-order terms?

They become negligible at scale. When n = 1,000,000:

• n² = 1,000,000,000,000

• n = 1,000,000

• The difference is 0.0001%

They do not change the growth curve. Whether you add 5000 or 5,000,000 to n², the dominant term is still n².

Simplification aids communication. "O(n²)" is clearer than "O(n² + 3n log n + 17n + 42)."

When constants do matter

Asymptotic notation is about behavior at scale, but constants matter in practice:

For moderate inputs: An O(n) algorithm with constant factor 1000 is slower than an O(n log n) algorithm with constant factor 1 until n exceeds a threshold. For your actual data size, the "slower" asymptotic algorithm might be faster.

For tight comparisons: When comparing two O(n log n) algorithms, constants decide the winner.

For resource-constrained systems: In embedded systems or real-time applications, a 2x constant factor might exceed available resources.

The solution: use asymptotic analysis to understand scaling, then benchmark to understand actual performance.

Big-O definition

f(n) = O(g(n)) if and only if there exist positive constants c and n₀ such that:

f(n) ≤ c·g(n) for all n ≥ n₀

In words: for sufficiently large inputs (beyond n₀), f(n) is bounded above by g(n) times some constant c.

Example: Prove that 3n + 10 = O(n)

• We need constants c and n₀ such that 3n + 10 ≤ c·n for all n ≥ n₀

• Choose c = 4 and n₀ = 10

• For n ≥ 10: 3n + 10 ≤ 3n + n = 4n ✓

Big-Omega definition

f(n) = Ω(g(n)) if and only if there exist positive constants c and n₀ such that:

f(n) ≥ c·g(n) for all n ≥ n₀

In words: for sufficiently large inputs, f(n) is bounded below by g(n) times some constant c.

Example: Prove that 3n + 10 = Ω(n)

• We need constants c and n₀ such that 3n + 10 ≥ c·n for all n ≥ n₀

• Choose c = 3 and n₀ = 1

• For n ≥ 1: 3n + 10 ≥ 3n ✓

Big-Theta definition

f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)).

Equivalently: there exist positive constants c₁, c₂, and n₀ such that:

c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀

Example: Prove that 3n + 10 = Θ(n)

• We showed 3n + 10 = O(n) with c = 4

• We showed 3n + 10 = Ω(n) with c = 3

• Therefore 3n + 10 = Θ(n) with c₁ = 3 and c₂ = 4

Why n₀ exists

The threshold n₀ allows us to ignore small-input behavior. Constants and lower-order terms might dominate for small n, but we only care about large-n behavior.

For example, n² < 1000n when n < 1000. But for n ≥ 1000, n² takes over. By choosing n₀ = 1000, we focus on the region where growth rate dominates.

"Big-O means worst case"

Not exactly. Big-O describes an upper bound on growth rate. It can be applied to:

• Worst-case analysis: the maximum operations for any input of size n

• Average-case analysis: the expected operations for random inputs of size n

• Best-case analysis: the minimum operations for any input of size n

You can say "the worst-case complexity is O(n²)" or "the average-case complexity is O(n)." The notation describes the bound; you specify which case you are analyzing.

By convention, when someone says "this algorithm is O(n²)" without qualification, they usually mean worst-case. But this is convention, not a property of the notation itself.

"O(n) is always faster than O(n²)"

Only asymptotically. For small n or large constant factors, an O(n²) algorithm might be faster in practice.

Consider:

• Algorithm A: 1000n operations (O(n))

• Algorithm B: n² + 10 operations (O(n²))

For n < 1000, Algorithm B is faster. For n > 1000, Algorithm A is faster.

Asymptotic notation describes behavior as n approaches infinity, not performance for any specific n.

"Always drop all constants"

While we drop constants in the final Big-O expression, we should still understand them. An O(n) algorithm that makes 100 passes over the data is meaningfully different from one that makes 2 passes, even though both are O(n).

When:

• Comparing algorithms with the same Big-O: constants decide the winner

• Working with fixed input sizes: constants affect actual runtime

• Optimizing within a complexity class: reducing constants helps

Dropping constants simplifies communication and comparison of growth rates. It does not mean constants are unimportant.

"Big-O is the only notation that matters"

Big-O is the most common, but:

• Lower bounds (Ω) prove fundamental limits and optimality

• Tight bounds (Θ) give maximum precision

• Understanding all three makes you a more rigorous analyst

In practice, most engineers use Big-O. In theory and research, all three notations are essential.

"Asymptotic analysis is always accurate"

Asymptotic analysis predicts behavior at scale, but:

• Real inputs have finite size

• Cache effects change performance characteristics

• Constant factors can dominate for practical input sizes

• Implementation details matter

Use asymptotic analysis to understand fundamental scaling, then validate with benchmarks on real data.

Common growth rate ordering

From slowest to fastest growth:

1. O(1) — constant

2. O(log log n) — iterated logarithmic

3. O(log n) — logarithmic

4. O((log n)^k) — polylogarithmic

5. O(n^c) for 0 < c < 1 — sublinear (e.g., O(√n))

6. O(n) — linear

7. O(n log n) — linearithmic

8. O(n²) — quadratic

9. O(n³) — cubic

10. O(n^k) for k > 1 — polynomial

11. O(2^n) — exponential

12. O(n!) — factorial

13. O(n^n) — superexponential

Each level grows dramatically faster than the previous.

The gap between classes

The difference between adjacent classes grows with input size:

The jump from polynomial to exponential is especially dramatic. This is why exponential algorithms are considered intractable for large inputs.

Useful comparisons

For any constant k > 0:

• log n < n^k (logarithms grow slower than any polynomial)

• n^{k < 2}n (polynomials grow slower than exponentials)

• n! > 2^n (factorial grows faster than exponential)

• n^n > n! (this grows even faster)

For any constants a < b:

• n^{a < n}b (smaller exponents grow slower)

• log n^a = a log n (exponents become coefficients)

Sequential operations (addition)

If you do operation A (O(f(n))) followed by operation B (O(g(n))):

• Total complexity: O(f(n) + g(n)) = O(max(f(n), g(n)))

The dominant term wins.

Example: An O(n) scan followed by an O(n²) search is O(n + n²) = O(n²).

Nested operations (multiplication)

If operation B (O(g(n))) runs inside operation A which iterates O(f(n)) times:

• Total complexity: O(f(n) · g(n))

The complexities multiply.

Example: For each of n elements (O(n)), you do a binary search (O(log n)). Total: O(n · log n) = O(n log n).

Conditional operations

If you do either operation A or operation B:

• Total complexity: O(max(f(n), g(n)))

You bound by the worst case.