Lembar kerja Algoritma & kompleksitas dengan jawaban

Manakah dari waktu eksekusi berikut yang polinomial?

1. AO(nⁿ)
2. BO(2ⁿ)
3. CO(n³)
4. DO(n!)

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

1. AWaktu eksekusinya tidak bertambah seiring ukuran input
2. BSelalu memerlukan tepat satu detik
3. CMemproses tepat satu elemen per detik waktu eksekusi
4. DHanya dapat dijalankan sekali

Apa syarat binary search terhadap inputnya?

1. AArray harus terurut
2. BArray hanya boleh berisi bilangan positif
3. CPanjang array harus pangkat dua
4. DArray tidak boleh berisi lebih dari 1000 elemen

Quicksort selalu memakai elemen pertama sebagai pivot. Pada input mana algoritma ini menunjukkan perilaku kasus terburuknya?

1. AArray yang semua elemennya berbeda
2. BArray dalam urutan acak
3. CArray dengan panjang 2
4. DArray yang sudah terurut

Berapa kompleksitas waktu kasus terburuk quicksort?

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

Rekurens T(n) = 2T(n − 1) + O(1) menghasilkan apa?

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

Apa perbedaan antara masalah undecidable dan masalah intractable?

1. ATidak ada algoritma yang menyelesaikan masalah undecidable untuk semua input, sedangkan masalah intractable dapat diselesaikan tetapi terlalu lambat
2. BKeduanya berarti masalah itu sama sekali tidak memiliki algoritma
3. CMasalah intractable tidak dapat diselesaikan oleh algoritma apa pun, sedangkan masalah undecidable hanya memerlukan waktu eksponensial
4. DMasalah undecidable berada di NP, sedangkan masalah intractable di P

Pernyataan mana tentang memilih elemen terkecil ke-k dari array tidak terurut yang benar?

1. AQuickselect berjalan dalam O(log n) pada kasus terburuk, karena hanya berekursi ke satu sisi pivot
2. BQuickselect berjalan dalam O(n) yang diharapkan, dan median-of-medians menjamin O(n) pada kasus terburuk
3. CSeleksi selalu memerlukan Ω(n log n) karena memerlukan pengurutan
4. DSeleksi hanya mungkin dilakukan dalam O(n²)