Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu kasus terburuk merge sort?

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

Apa arti f(n) = Θ(g(n))?

1. Af tumbuh benar-benar lebih lambat daripada g
2. Bf tumbuh dengan laju yang sama dengan g, dibatasi di atas dan di bawah oleh kelipatan konstan g
3. Cf selalu lebih kecil daripada g untuk setiap n, sehingga g membatasinya dari atas tetapi tidak pernah dari bawah
4. Df tumbuh benar-benar lebih cepat daripada g

Pertumbuhan O(2ⁿ) disebut apa?

1. AEksponensial
2. BLinear
3. CLogaritmik
4. DPolinomial

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

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

Berapa kompleksitas waktu algoritma Bellman–Ford pada graf dengan V simpul dan E sisi?

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

Pemrograman dinamis (dynamic programming) berguna ketika suatu masalah memiliki:

1. AHanya input acak
2. BSubmasalah yang tumpang tindih dan substruktur optimal
3. CSatu loop saja
4. DTidak ada submasalah sama sekali, sehingga dapat diselesaikan dalam satu langkah

Mengapa setiap pencarian berbasis perbandingan dalam array terurut memerlukan Ω(log n) perbandingan pada kasus terburuk?

1. APohon keputusan dengan n kemungkinan hasil harus memiliki kedalaman setidaknya log₂ n
2. BBinary search adalah satu-satunya algoritma yang mungkin, dan memerlukan log₂ n perbandingan
3. CSetiap elemen harus dibandingkan setidaknya sekali
4. DSetiap perbandingan memerlukan waktu logaritmik

Masalah penghentian (halting problem) menunjukkan bahwa:

1. ABeberapa program berjalan lebih cepat di komputer yang lebih cepat, sehingga berhenti atau tidaknya bergantung pada perangkat keras
2. BSetiap program pada akhirnya akan berhenti
3. CTidak ada algoritma yang dapat memutuskan untuk setiap program dan input apakah program tersebut akan berhenti
4. DLoop sebaiknya dihindari