Doubling the data for an O(n²) algorithm
An algorithm has a time complexity of O(n²). It takes 3 seconds to process 1000 data items.
Approximately how long will it take to process 2000 data items?
A 3 seconds
B 6 seconds
C 12 seconds
D 9 seconds
[1]
- 1
Use the growth rate. For O(n²), the time grows with the square of the number of items. Doubling n multiplies the time by 2² = 4.
- 2
3 seconds × 4 = 12 seconds. Answer C (1).
B (6 seconds) is what an O(n) algorithm would take; D treats the growth as × 3.
Answer
C
Examiner tip
Examiner tip: Big O describes how the time grows as n grows, not the time itself. Ask what happens to n², n or log n when n is doubled: O(n) doubles, O(n²) quadruples, O(log n) adds one step.
Common mistake: choosing B because the data doubled. That is linear growth, O(n).