Sebuah algoritma pengurutan (sorting) memiliki kompleksitas waktu O(n log n). Jika waktu eksekusi untuk 1000 data adalah 2 detik, berapa perkiraan waktu eksekusi untuk 8000 data?

Jawaban: 16 detik

Dengan O(n log n), waktu sebanding dengan n log n. Untuk n=1000, n log n = 1000 × 10 = 10.000. Untuk n=8000, n log n = 8000 × 13 = 104.000. Rasio = 10.4, sehingga waktu ≈ 2 × 10.4 = 20.8 detik, dibulatkan menjadi 21 detik. Namun pilihan yang paling mendekati adalah 16 detik? Sebenarnya perhitungan tepat: log2(1000) ≈ 9.97, log2(8000) ≈ 12.97. Rasio = (8000×12.97)/(1000×9.97) ≈ 10.4. Jadi waktunya ≈ 20.8 detik. Tidak ada opsi yang tepat. Soal perlu diperbaiki. (Catatan: soal ini dianggap tidak valid karena opsi tidak sesuai. Akan diganti.)