Practice question · Fill in the blanks
Complete the description of big-O notation.
Big-O keeps only ______ because it describes behaviour as n grows without bound.
Word bank: the constant factor · the dominant term · the smallest term · the exact step count
Hints
- Which part of 3n squared + 500n + 900 wins for very large n?
- Constants and lower-order terms are deliberately discarded.
Show the answer
Big-O keeps only the dominant term because it describes behaviour as n grows without bound.
Why
For large n the fastest-growing term swamps everything else, so only it is kept. That is why 3n squared + 500n + 900 is simply quadratic, and why O(n) and O(100n) name the same class.
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
- Select every statement about big-O notation that is TRUE.
- 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…
- An O(n²) algorithm can beat an O(n log n) one on real data. Why does big-O notation not settle which program…