Lembar kerja Algoritma & kompleksitas dengan jawaban

Algoritma dengan dua loop bersarang, yang masing-masing berjalan n kali, biasanya memiliki kompleksitas apa?

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

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

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

Apa yang digambarkan oleh waktu eksekusi kasus rata-rata?

1. AWaktu yang diharapkan atas distribusi input berukuran n tertentu
2. BNilai tengah antara waktu eksekusi kasus terbaik dan kasus terburuk
3. CWaktu pada komputer yang paling umum
4. DWaktu untuk input dengan panjang rata-rata

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

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

Berapa kompleksitas waktu dari: for i = 1 to n: for j = 1 to i: lakukan kerja O(1)?

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

Apakah benar mengatakan bahwa algoritma O(n²) juga O(n³)?

1. ATidak, karena n³ lebih kecil daripada n² untuk n besar
2. BYa, karena Big O adalah batas atas dan n² tidak tumbuh lebih cepat daripada n³
3. CTidak, karena Big O harus selalu menyatakan laju pertumbuhan yang tepat dari fungsi itu
4. DYa, tetapi hanya jika n lebih kecil dari 100

Berapa biaya waktu dan ruang untuk menghitung bilangan Fibonacci ke-n dengan loop yang hanya menyimpan dua nilai terakhir?

1. AWaktu O(2ⁿ) dan ruang O(1)
2. BWaktu O(log n) dan ruang O(n)
3. CWaktu O(n) dan ruang O(1)
4. DWaktu O(n) dan ruang O(n)

Apa akibatnya jika seseorang menemukan algoritma waktu polinomial untuk satu masalah NP-complete?

1. ASetiap masalah di NP dapat diselesaikan dalam waktu polinomial, sehingga P = NP
2. BHalting problem menjadi decidable
3. CHanya masalah itu yang pindah ke P
4. DSemua algoritma berwaktu eksponensial seketika berjalan dalam waktu linear