Data Structures and Algorithms
A program with O(n²) time complexity takes 0.5 seconds for 1,000 data items. About how long will it take for 4,000 items?
- A2 seconds
- B8 seconds
- C32 seconds
Show answer and explanation
Answer: B. 8 seconds
With O(n²), the running time is proportional to the square of the data size, so four times the data takes 4² = 16 times as long: 0.5 s × 16 = 8 s. 2 seconds would be the result for O(n), which is proportional to the data size, and 32 seconds for O(n³), which grows with the cube (4³ = 64 times). In practice it can be even slower, for example once the data no longer fits in the cache.
- A. That would be the case for O(n), which grows in proportion to the data size; with O(n²) the growth is squared.
- B. Correct. Four times the data takes 4² = 16 times as long: 0.5 × 16 = 8 seconds.
- C. This is the value for O(n³), which grows 4³ = 64 times.