Lembar kerja Algoritma & kompleksitas dengan jawaban

Notasi manakah yang menyatakan batas bawah (lower bound) pertumbuhan?

1. Ao (little o)
2. BO (Big O)
3. CΘ (Big Theta)
4. DΩ (Big Omega)

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. C6 detik
4. D9 detik

Algoritma O(n²) memerlukan 1 detik untuk n = 1000. Kira-kira berapa lama untuk n = 2000?

1. A4 detik
2. B2 detik
3. C8 detik
4. D1 detik

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

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

Pada activity selection problem, aturan greedy mana yang selalu menghasilkan jumlah maksimum aktivitas yang tidak saling tumpang tindih?

1. APilih aktivitas yang dimulai paling awal
2. BPilih aktivitas terpendek terlebih dahulu
3. CPilih aktivitas yang selesai paling awal, lalu ulangi dengan aktivitas yang kompatibel
4. DPilih aktivitas dengan tumpang tindih paling sedikit terlebih dahulu, lalu ulangi dengan aktivitas yang kompatibel

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. CMerge sort sudah O(n)
4. DDynamic programming hanya bekerja pada masalah graf, bukan pada array

Mengapa pencarian rata-rata pada tabel hash adalah O(1) tetapi kasus terburuknya O(n)?

1. AKunci harus diurutkan terlebih dahulu
2. BAkses array memerlukan O(n)
3. CFungsi hash lambat
4. DBanyak kunci dapat bertabrakan (collision) di bucket yang sama

Bagaimana perbandingan n! dan 2ⁿ untuk n besar?

1. AKeduanya tumbuh dengan laju yang sama
2. Bn! tumbuh lebih cepat daripada 2ⁿ
3. C2ⁿ tumbuh lebih cepat daripada n!
4. Dn! adalah O(n²)