Practice question · Select all that apply
Select every statement about big-O notation that is TRUE.
Hints
- Two options attribute a precision to big-O that it deliberately refuses.
- Big-O says nothing about seconds or about the machine.
Show the answer
- A. The dominant term determines the class
- C. Halving the remaining problem at each step gives logarithmic growth
- D. For large n, a linearithmic sort scales better than a quadratic one
Why
Big-O drops constants and lower-order terms and describes growth, not wall-clock time; the other three statements are exact. Wanting big-O to predict seconds is the commonest misreading of it.
Practise Computational Complexity
The app has 5 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.
More questions on Computational Complexity
- Match each complexity class to an operation that has it.
- Order these complexity classes from the slowest-growing to the fastest-growing.
- A quadratic algorithm takes 4 seconds on an input of size 1000. Assuming the quadratic model holds, roughly…
- Binary search halves the remaining portion of a sorted list at each step. Starting from 1024 items, how many…
- Binary search is O(log n) and needs sorted data; a linear scan is O(n) and needs nothing. For a list searched…
- Complete the description of big-O notation.
- An O(n²) algorithm can beat an O(n log n) one on real data. Why does big-O notation not settle which program…