Questions: Algorithm Complexity and Big-O Notation

Question 1

Algorithm A runs in O(n) time and Algorithm B runs in O(n²) time. A student claims A is always faster than B for any input size. What is the strongest counterargument?

• A. The claim is correct — linear algorithms are always faster than quadratic ones
• B. Big-O only describes asymptotic behavior; for small inputs or with large constant factors, A could actually run slower than B in practice
• C. The claim is wrong because O(n) and O(n²) describe memory usage, not runtime
• D. The student should compare Ω bounds instead of O bounds to determine which is faster

Answer: (B)

Big-O ignores constant factors and describes behavior as n → ∞. An O(n) algorithm with a huge hidden constant (e.g., 10⁶ · n operations) runs slower than an O(n²) algorithm with a tiny constant (e.g., n²/1000) for all practical input sizes. Big-O classifies growth rates; it is not a performance oracle. For the inputs you actually encounter, profiling still matters.

Question 2

Suppose f(n) = 1000n and g(n) = n². Which statement is true?

• A. f is Θ(g) because both are polynomial functions
• B. f and g have the same Big-O class because both involve n
• C. f is O(g) but g is NOT O(f)
• D. g is O(f) because n² = n × n involves the same n as f

Answer: (C)

f(n) = 1000n satisfies f(n) ≤ 1000 · g(n) = 1000n² for all n ≥ 1, so f is O(g). But g(n) = n² is NOT O(f) = O(n): there is no constant c such that n² ≤ c · n for all large n, because n²/n = n grows without bound. Big-O is not symmetric — O(n) ⊊ O(n²) strictly.

Question 3

An algorithm proved to be Θ(n log n) is also O(n log n).

• T. True
• F. False

Answer: True

Θ(g) means both O(g) (upper bound) and Ω(g) (lower bound) hold simultaneously. So Θ(n log n) implies O(n log n). The converse is not always true: O(n log n) alone allows the algorithm to be faster (e.g., O(n)), but Θ pins it to exactly that growth rate.

Question 4

The statement 'comparison-based sorting requires Ω(n log n) comparisons' means that no specific known sorting algorithm can do better — but a hypothetical future algorithm might.

• T. True
• F. False

Answer: False

Ω(n log n) here is a lower-bound theorem about all possible comparison-based sorting algorithms, not just known ones. It is proved by showing that any decision tree for sorting n elements must have at least n! leaves, requiring depth ≥ log₂(n!) = Ω(n log n). No future algorithm can circumvent this if it uses only comparisons to determine order — it is a mathematical impossibility, not a current limitation.

Question 5

Why does the formal definition of Big-O (f(n) ≤ c · g(n) for all n ≥ n₀) justify dropping constant factors and lower-order terms?

Model answer: The constant c absorbs any multiplicative constant: if f(n) = 5n², then f = O(n²) because 5n² ≤ 5 · n² with c = 5. Lower-order terms are absorbed because for large enough n, the dominant term grows large enough to subsume them — e.g., n² + 100n ≤ 2n² for all n ≥ 100. The threshold n₀ lets us ignore any finite initial region. Together, c and n₀ make Big-O scale-invariant and focused purely on growth rate.

This is the key insight behind Big-O as a classification tool: it strips away everything that depends on hardware, implementation details, or small inputs, leaving only the fundamental growth behavior. An algorithm is O(n²) not because it runs in exactly n² steps, but because its operation count is bounded above by some multiple of n² for all large inputs.