Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu untuk mencari nilai terbesar dalam array tidak terurut berisi n bilangan?

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

Algoritma pengurutan manakah yang berulang kali menukar elemen bersebelahan yang urutannya salah?

1. ABubble sort
2. BHeap sort
3. CMerge sort
4. DQuicksort

Berapa nilai log₂ 1024?

1. A32
2. B12
3. C10
4. D512

Mengapa dynamic programming tidak benar-benar mempercepat merge sort?

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

Apa artinya suatu masalah memiliki optimal substructure?

1. ASetiap submasalah memiliki ukuran yang sama
2. BMasalah itu memiliki tepat satu solusi optimal, yang dimiliki bersama oleh setiap submasalah
3. CSolusi optimal dapat dibangun dari solusi optimal submasalahnya
4. DMasalah itu dapat diselesaikan dalam waktu konstan

Berapa banyak ruang stack yang dipakai fungsi faktorial rekursif sederhana fact(n) = n × fact(n − 1)?

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

Algoritma manakah yang menemukan pohon rentang minimum dengan berulang kali menambahkan sisi termurah yang tidak membentuk siklus?

1. AAlgoritma Kruskal
2. BFloyd–Warshall
3. CAlgoritma Dijkstra
4. DAlgoritma Prim yang dimulai dari satu simpul

Apakah 2²ⁿ termasuk O(2ⁿ)?

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