Lembar kerja Algoritma & kompleksitas dengan jawaban

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

1. A9 detik
2. B12 detik
3. C6 detik
4. D3 detik

Apa artinya jika suatu operasi berjalan dalam waktu O(1)?

1. ASelalu memerlukan tepat satu detik
2. BWaktu eksekusinya tidak bertambah seiring ukuran input
3. CHanya dapat dijalankan sekali
4. DMemproses tepat satu elemen per detik waktu eksekusi

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

1. A8 detik
2. B2 detik
3. C4 detik
4. D1 detik

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

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

Mengapa dynamic programming tidak benar-benar mempercepat merge sort?

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

Berapa kompleksitas waktu algoritma dynamic programming standar untuk longest common subsequence dari string dengan panjang m dan n?

1. AO(mn log n)
2. BO(mn)
3. CO(m + n)
4. DO(2^m+n)

Pernyataan mana tentang memilih elemen terkecil ke-k dari array tidak terurut yang benar?

1. ASeleksi selalu memerlukan Ω(n log n) karena memerlukan pengurutan
2. BSeleksi hanya mungkin dilakukan dalam O(n²)
3. CQuickselect berjalan dalam O(n) yang diharapkan, dan median-of-medians menjamin O(n) pada kasus terburuk
4. DQuickselect berjalan dalam O(log n) pada kasus terburuk, karena hanya berekursi ke satu sisi pivot

Masalah knapsack 0/1 yang diselesaikan dengan pemrograman dinamis memerlukan waktu O(nW). Mengapa ini disebut pseudo-polinomial?

1. AKarena algoritma ini hanya berlaku untuk W = 0
2. BW adalah nilai numerik, sehingga waktunya eksponensial terhadap jumlah bit yang diperlukan untuk menuliskan W
3. CKarena algoritmanya bersifat acak (randomised) dan waktu eksekusinya berbeda untuk setiap input
4. DKarena n selalu kecil