Questions: Asymptotic Notation: Big-O, Big-Omega, Big-Theta

Question 1

An algorithm performs exactly 3n² + 50n + 200 operations for an input of size n. What is its Big-O complexity?

• A. O(3n² + 50n + 200) — the exact operation count must be preserved
• B. O(n²) — lower-order terms and constant factors are absorbed
• C. O(50n) — the linear term dominates for practical input sizes
• D. O(n² + n) — both the quadratic and linear terms must be included

Answer: (B)

Big-O captures the dominant growth rate by absorbing constant factors and lower-order terms. For large n, 3n² + 50n + 200 grows proportionally to n² — the factor of 3 is absorbed into the Big-O constant c, and 50n and 200 become negligible relative to n² as n grows. O(3n²) and O(n²) describe the same asymptotic class. This is the core insight: Big-O is about growth shape, not actual operation count. The misconception is thinking the exact formula must be preserved, but Big-O explicitly discards everything except the dominant term's shape.

Question 2

Algorithm A is O(n²) and Algorithm B is O(n log n). Which conclusion is best supported?

• A. Algorithm B is always faster than A, regardless of input size
• B. Algorithm A will always take longer on any input of size n
• C. For sufficiently large inputs, B will scale better than A, but A may be faster for small inputs due to constant factors
• D. The two algorithms have equivalent performance when constant factors are accounted for

Answer: (C)

Asymptotic notation makes claims about growth rates for large n — it says nothing about performance on small inputs. Algorithm A might have a very small constant factor making it faster in practice for n = 10 or n = 100. Big-O complexity is not a guarantee of absolute speed; it is a guarantee about how each algorithm scales as n grows. Once n is large enough that the n² vs. n log n difference dominates any constant factor, B will outperform A. The 'for sufficiently large inputs' qualifier is essential.

Question 3

If f(n) is Θ(g(n)), then f(n) is both O(g(n)) and Ω(g(n)).

• T. True
• F. False

Answer: True

Big-Theta is defined as the intersection of both bounds: f(n) = Θ(g(n)) means f(n) = O(g(n)) AND f(n) = Ω(g(n)). The Big-O bound says f grows no faster than g; the Big-Omega bound says f grows no slower than g. Together they pin down the growth rate precisely from both above and below. Merge sort is the classic example: it is Θ(n log n) because it always requires time proportional to n log n — never dramatically more, never significantly less.

Question 4

O(2n) and O(n) are different complexity classes because the first algorithm usually runs exactly twice as fast as the second.

• T. True
• F. False

Answer: False

O(2n) and O(n) are the same complexity class. Big-O notation absorbs constant factors: f(n) is O(g(n)) if there exist constants c and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀. Choosing c = 2 in the definition of O(n) absorbs the factor of 2, so 2n = O(n). Both functions grow linearly — doubling n doubles runtime in either case. The difference between O(2n) and O(n) is a constant factor, not a difference in growth rate, and Big-O ignores constant factors by design.

Question 5

Explain why Big-O notation drops constant factors (like the 3 in O(3n²)), and why this makes the notation useful for comparing algorithms.

Model answer: Constant factors depend on hardware, compiler, and implementation details — they are not intrinsic to the algorithm. An O(n²) algorithm runs twice as fast on hardware that is twice as fast, but it is still O(n²). By absorbing constants, Big-O captures the growth shape that persists regardless of these extrinsic factors. This makes cross-algorithm comparison meaningful: saying one algorithm is O(n) and another is O(n²) tells you that the first will eventually outperform the second on any hardware, for large enough inputs, regardless of how the constants differ.

Big-O answers 'how does this scale?' rather than 'how fast does this run on my laptop?' For small inputs, the constant matters enormously — an O(n²) algorithm with a tiny constant might beat an O(n log n) algorithm with a large constant. But as n grows, the growth rate dominates. The notation is designed for the scaling question, and for that question, constants are irrelevant. This is also why recognizing complexity class is the first step in algorithm evaluation: it tells you whether the algorithm is even in the right ballpark for large inputs before you worry about constants.