Which of the following is NOT a valid Big-O upper bound for f(n) = 3n² + 100n?
AO(n²)
BO(n³)
CO(n² + n)
DO(n)
O(n) is not valid because 3n² + 100n grows faster than any constant multiple of n. The others are all valid upper bounds: O(n²) is the tightest, O(n³) is a looser upper bound, and O(n² + n) is redundant but technically correct. Understanding which bounds are valid (even if not tight) is essential for reasoning about algorithm complexity.
Question 2 True / False
An algorithm that runs in O(n²) time is typically slower in practice than one that runs in O(n log n) time.
TTrue
FFalse
Answer: False
Big-O describes asymptotic behavior as n → ∞ and ignores constant factors. For small inputs, an O(n²) algorithm with a tiny constant could easily outperform an O(n log n) algorithm with a large constant. The asymptotic crossover point may be at n = 10⁶ or higher. Always consider actual input sizes and constant factors when choosing algorithms in practice.
Question 3 Short Answer
What is the key difference between O(g(n)), Ω(g(n)), and Θ(g(n))?
Think about your answer, then reveal below.
Model answer: O gives an asymptotic upper bound (f grows no faster than g), Ω gives a lower bound (f grows at least as fast as g), and Θ means both simultaneously — f grows at exactly the same asymptotic rate as g.
Knowing only an upper bound is often insufficient: a function that is O(n²) might actually run in O(n). Θ-notation is the precise characterization of asymptotic equivalence. In practice, Θ is more informative when provable, but O is used more commonly because lower bounds are harder to establish.