某個時間複雜度為 O(n²) 的程式，在資料數為1,000時處理時間為0.5秒。若資料數變為4,000，處理時間約為幾秒？

正確答案：B. 8秒

O(n²) 的處理時間與資料數的平方成正比，因此資料數變為4倍時，處理時間變為 4² = 16倍，0.5秒 × 16 = 8秒。2秒是與資料數成正比的 O(n) 的情況，32秒則是與立方成正比的 O(n³) 的情況（4³ = 64倍）。實際上，也可能因資料放不進快取等影響而變得更慢。

• A. 若是與資料數成正比的 O(n)，會是4倍的2秒，但 O(n²) 是以平方增加。
• B. 正確。資料變為4倍時為 4² = 16倍，0.5 × 16 = 8秒。
• C. 這是以 4³ = 64倍計算的 O(n³) 的值。