Lembar kerja Algoritma & kompleksitas dengan jawaban

Algoritma O(n) memerlukan 3 detik untuk n = 1 juta. Kira-kira berapa lama untuk n = 2 juta?

1. A3 detik
2. B9 detik
3. C12 detik
4. D6 detik

Berapa kompleksitas waktu kasus terbaik insertion sort, pada array yang sudah terurut?

1. AO(n²)
2. BO(n log n)
3. CO(1)
4. DO(n)

Apa artinya jika suatu operasi berjalan dalam waktu O(1)?

1. ASelalu memerlukan tepat satu detik
2. BWaktu eksekusinya tidak bertambah seiring ukuran input
3. CHanya dapat dijalankan sekali
4. DMemproses tepat satu elemen per detik waktu eksekusi

Apa yang diukur oleh analisis amortisasi?

1. ABiaya algoritma pada input terbaik
2. BBiaya yang diharapkan atas input acak
3. CBiaya satu operasi yang paling mahal di mana pun dalam urutan itu
4. DBiaya rata-rata per operasi atas urutan operasi kasus terburuk

Berapa kompleksitas waktu menghitung bilangan Fibonacci ke-n dengan tabel bottom-up?

1. AO(n)
2. BO(n²)
3. CO(2ⁿ)
4. DO(log n)

Mengapa basis logaritma biasanya tidak dituliskan dalam Big O, seperti pada O(log n)?

1. ALogaritma dengan basis berbeda hanya berbeda faktor konstan
2. BSemua logaritma dalam ilmu komputer berbasis 10, sehingga basisnya tersirat
3. CBasis hanya berpengaruh untuk n kecil
4. DLogaritma selalu dibulatkan menjadi bilangan bulat

Pernyataan manakah tentang P dan NP yang benar?

1. ASetiap masalah di P juga termasuk dalam NP
2. BMasalah NP tidak dapat diverifikasi dengan cepat
3. CNP berarti "not polynomial"
4. DTelah dibuktikan bahwa P ≠ NP

Insertion sort berjalan dalam O(n) pada input terurut. Apakah ini bertentangan dengan batas bawah Ω(n log n) untuk pengurutan berbasis perbandingan?

1. AYa, tetapi hanya untuk array yang lebih pendek dari 100
2. BTidak, batas bawah itu berlaku untuk kasus terburuk atas semua input, bukan untuk setiap input
3. CYa, sehingga batas bawah itu salah
4. DTidak, karena insertion sort bukan pengurutan berbasis perbandingan