Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa banyak memori tambahan yang dipakai merge sort standar berbasis array?

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

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

1. AΘ (Big Theta)
2. BΩ (Big Omega)
3. CO (Big O)
4. Do (little o)

Bagaimana cara kerja selection sort?

1. AMenyisipkan setiap elemen ke bagian terurut yang terus bertambah dengan menggeser
2. BBerulang kali mencari minimum dari bagian yang belum terurut lalu menukarnya ke depan
3. CBerulang kali menukar elemen bersebelahan yang urutannya salah
4. DMembagi array menjadi dua bagian lalu menggabungkannya

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

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

Relasi rekurens T(n) = 2T(n/2) + O(n) memiliki solusi:

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

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

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

Mengapa setiap pencarian berbasis perbandingan dalam array terurut memerlukan Ω(log n) perbandingan pada kasus terburuk?

1. ABinary search adalah satu-satunya algoritma yang mungkin, dan memerlukan log₂ n perbandingan
2. BSetiap perbandingan memerlukan waktu logaritmik
3. CSetiap elemen harus dibandingkan setidaknya sekali
4. DPohon keputusan dengan n kemungkinan hasil harus memiliki kedalaman setidaknya log₂ n

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

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