Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu depth-first search pada graf yang disimpan sebagai adjacency list?

1. AO(V²)
2. BO(E log V)
3. CO(V + E)
4. DO(V × E)

Berapa kompleksitas waktu kasus terburuk merge sort?

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

Pertumbuhan O(2ⁿ) disebut apa?

1. ALinear
2. BEksponensial
3. CLogaritmik
4. DPolinomial

Berapa banyak ruang stack yang dipakai fungsi faktorial rekursif sederhana fact(n) = n × fact(n − 1)?

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

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

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

Batas bawah untuk pengurutan berbasis perbandingan pada kasus terburuk adalah:

1. AΩ(log n)
2. BΩ(n log n)
3. CΩ(n²)
4. DΩ(n)

Apa perbedaan antara masalah undecidable dan masalah intractable?

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

Teknik manakah yang memberikan waktu eksekusi harapan (expected) O(n log n) untuk quicksort pada input apa pun?

1. AMengurutkan input sebelum menjalankan quicksort
2. BMemilih pivot secara acak seragam
3. CSelalu memilih elemen pertama
4. DMenggunakan rekursi hanya pada sisi kiri