Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu kasus terburuk insertion sort?

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

Kelas kompleksitas manakah yang tumbuh paling cepat untuk n yang besar?

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

Berapa kompleksitas waktu binary search pada array yang sudah terurut?

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

Algoritma manakah yang menemukan lintasan terpendek dari satu sumber pada graf dengan bobot sisi non-negatif?

1. AAlgoritma Kruskal
2. BBellman–Ford diperlukan dalam semua kasus
3. CDepth-first search (DFS)
4. DAlgoritma Dijkstra

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

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

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

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

Masalah penghentian (halting problem) menunjukkan bahwa:

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

Pernyataan mana tentang notasi little-o yang benar?

1. A2n = o(n), karena 2n tumbuh lambat
2. Bn = o(n²), tetapi n bukan o(n)
3. Cn² = o(n)
4. Dn = o(n), karena setiap fungsi adalah little-o dari dirinya sendiri