Practice question · Numerical answer
A quadratic algorithm takes 4 seconds on an input of size 1000. Assuming the quadratic model holds, roughly how many seconds does it take on an input of size 3000?
Hints
- Quadratic means the time scales with the square of the size.
- Tripling the input multiplies the work by 3 squared.
Show the answer
36
Why
Tripling n multiplies quadratic work by 9, so 4 seconds becomes 36. Note that the constant factor never had to be known, that is exactly the information big-O throws away and still predicts correctly.
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.
- 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…