Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu binary search pada array yang sudah terurut?

1. AO(n log n)
2. BO(log 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. CBaris pertama fungsi
4. DPemanggilan yang memakai memori paling banyak

Apa yang digambarkan oleh waktu eksekusi kasus terburuk suatu algoritma?

1. AWaktu yang diharapkan pada input acak berukuran n
2. BWaktu maksimum yang diperlukan atas semua input berukuran n
3. CWaktu yang diperlukan pada komputer yang lambat
4. DWaktu yang diperlukan pada input terkecil

Apa yang dihitung algoritma Floyd–Warshall, dan seberapa cepat?

1. AUrutan topologis dalam O(V²)
2. BLintasan terpendek dari satu simpul sumber ke semua simpul lain dalam O(V + E)
3. CLintasan terpendek antara semua pasangan simpul dalam O(V³)
4. DMinimum spanning tree dalam O(E log V)

Quicksort selalu memakai elemen pertama sebagai pivot. Pada input mana algoritma ini menunjukkan perilaku kasus terburuknya?

1. AArray dalam urutan acak
2. BArray yang sudah terurut
3. CArray yang semua elemennya berbeda
4. DArray dengan panjang 2

Berapa waktu eksekusi LSD radix sort pada n bilangan bulat dengan d digit dalam basis k?

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

Berapa biaya amortisasi menaikkan (increment) penghitung biner, mengingat satu increment dapat membalik banyak bit?

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

Apa yang ditetapkan oleh teorema Cook–Levin?

1. ASetiap masalah NP dapat diselesaikan dalam waktu eksponensial
2. BHalting problem tidak dapat diputuskan (undecidable)
3. CP tidak sama dengan NP
4. DBoolean satisfiability problem (SAT) adalah NP-complete