Practice question · Select all that apply
Select every true statement about complexity analysis.
Hints
- One option contradicts the rule about dropping constants.
- Recall quicksort's average versus worst case.
Show the answer
- B. Lower-order terms drop out, so n squared plus n is simply quadratic.
- C. Quicksort is O(n log n) on average but O(n^2) in the worst case
- D. Big-Theta is a tight bound
- E. Space complexity measures how memory grows with input size
Why
Dropping lower-order terms, tight bounds, quicksort's cases, and space complexity are all as taught. Keeping constant factors in a Big-O answer is exactly what the pitfall warns against.
Practise Complexity Analysis
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.