Which statement correctly applies the definition of Big-O as an asymptotic upper bound?
A5n is O(n) but cannot be O(n²), since n is a tighter bound
Bn² + 100n is Θ(n² + 100n) and cannot be simplified
CA function that is O(n) is also O(n²), since any upper bound of O(n) is also an upper bound of O(n²)
DBig-O and Big-Θ always refer to the same growth class
If f(n) = O(n), then there exist constants C and n₀ with f(n) ≤ C·n for n ≥ n₀. Since n ≤ n² for large n, the same C works to show f(n) ≤ C·n² — so f is also O(n²). Big-O is an upper bound, not an equality; saying a function is O(n²) does not mean it grows like n². Option A is a common misconception: O(n) does not exclude O(n²). Option B is wrong because Θ(n² + 100n) = Θ(n²) — lower-order terms are dropped.
Question 2 True / False
An algorithm with O(n²) worst-case complexity typically performs exactly n² operations on an input of size n.
TTrue
FFalse
Answer: False
Big-O gives an asymptotic upper bound, not an exact count. The actual number of operations might be 3n² + 5n + 2, or it might be n²/2 + 10. Constants and lower-order terms are deliberately ignored. Additionally, the worst-case complexity says nothing about how the algorithm performs on average or best-case inputs — an O(n²) algorithm might run in O(n) time on already-sorted data.
Question 3 Short Answer
What is the difference between saying f(n) = O(g(n)) and f(n) = Θ(g(n))?
Think about your answer, then reveal below.
Model answer: O(g(n)) means g is an asymptotic upper bound on f — f grows no faster than g, but could be much slower. Θ(g(n)) means g is both an upper and lower bound — f and g grow at the same asymptotic rate (f is sandwiched between two constant multiples of g). For example, n = O(n²) but n ≠ Θ(n²); however, 2n + 7 = Θ(n).
Θ is strictly stronger than O: every Θ relationship implies an O relationship, but not vice versa. When analyzing algorithms, Θ tells you the exact growth class; O tells you only a ceiling. Engineers often say 'O(n log n)' when they technically mean Θ(n log n) — the precise term when both upper and lower bounds are established.