Lembar kerja Algoritma & kompleksitas dengan jawaban

Sebuah loop dimulai dengan i = 1 dan menggandakan i setiap iterasi sampai i > n. Berapa kali loop itu berjalan?

1. ASekitar log₂ n
2. BSekitar n
3. CSekitar n²
4. DSekitar n / 2

Berapa kompleksitas waktu linear search pada array tidak terurut berisi n elemen (kasus terburuk)?

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

Apa yang dimaksud base case pada fungsi rekursif?

1. AKasus dengan input terbesar, yang ditangani sebelum pemanggilan rekursif apa pun
2. BKasus yang dijawab langsung tanpa melakukan pemanggilan rekursif lagi
3. CPemanggilan yang memakai memori paling banyak
4. DBaris pertama fungsi

Berapa kompleksitas waktu algoritma Bellman–Ford pada graf dengan V simpul dan E sisi?

1. AO(E log V)
2. BO(V × E)
3. CO(V + E)
4. DO(V³ × E)

Pernyataan mana tentang fungsi rekursif tanpa base case yang dapat dicapai yang benar?

1. AFungsi itu terus memanggil dirinya sendiri sampai call stack meluap (overflow)
2. BFungsi itu berjalan dalam waktu O(1)
3. CKompiler selalu mengubahnya menjadi loop yang berakhir dengan aman
4. DFungsi itu otomatis mengembalikan 0

Berapa kompleksitas waktu menghitung bilangan Fibonacci ke-n dengan tabel bottom-up?

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

Insertion sort berjalan dalam O(n) pada input terurut. Apakah ini bertentangan dengan batas bawah Ω(n log n) untuk pengurutan berbasis perbandingan?

1. ATidak, batas bawah itu berlaku untuk kasus terburuk atas semua input, bukan untuk setiap input
2. BYa, tetapi hanya untuk array yang lebih pendek dari 100
3. CTidak, karena insertion sort bukan pengurutan berbasis perbandingan
4. DYa, sehingga batas bawah itu salah

Manakah dari masalah satisfiability berikut yang diketahui dapat diselesaikan dalam waktu polinomial?

1. A2-SAT, dengan setiap klausa berisi paling banyak dua literal
2. BSAT umum pada formula dalam bentuk normal konjungtif
3. C3-SAT, dengan setiap klausa berisi tepat tiga literal
4. DCircuit satisfiability