Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu binary search pada array yang sudah terurut?

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

Algoritma O(n) memerlukan 3 detik untuk n = 1 juta. Kira-kira berapa lama untuk n = 2 juta?

1. A3 detik
2. B12 detik
3. C9 detik
4. D6 detik

Berapa waktu eksekusi counting sort untuk n bilangan bulat dalam rentang 0 sampai k?

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

Berapa kompleksitas waktu teramortisasi (amortised) untuk menambahkan elemen ke array dinamis yang menggandakan kapasitasnya ketika penuh?

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

Mengapa dynamic programming tidak benar-benar mempercepat merge sort?

1. AMerge sort tidak memiliki struktur rekursif
2. BSubmasalahnya tidak tumpang tindih, sehingga tidak ada yang dapat dipakai ulang
3. CDynamic programming hanya bekerja pada masalah graf, bukan pada array
4. DMerge sort sudah O(n)

Breadth-first search (BFS) pada graf tak berbobot menemukan:

1. APohon rentang minimum
2. BLintasan terpendek pada graf yang memiliki bobot sisi negatif
3. CLintasan terpendek berdasarkan jumlah sisi dari simpul awal
4. DUrutan topologis pada semua graf

Masalah penghentian (halting problem) menunjukkan bahwa:

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

Apakah 2²ⁿ termasuk O(2ⁿ)?

1. AYa, karena faktor konstan pada pangkat selalu diabaikan dalam Big O
2. BTidak, karena 2²ⁿ = 4ⁿ dan 4ⁿ / 2ⁿ = 2ⁿ tumbuh tanpa batas
3. CTidak, karena 2²ⁿ tumbuh lebih lambat daripada 2ⁿ
4. DYa, karena keduanya eksponensial