Lembar kerja Algoritma & kompleksitas dengan jawaban

Kelas kompleksitas manakah yang tumbuh paling cepat untuk n yang besar?

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

Berapa kompleksitas waktu kasus terbaik insertion sort, pada array yang sudah terurut?

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

Strategi desain apa yang digunakan merge sort?

1. ADivide and conquer (bagi dan taklukkan)
2. BPilihan greedy
3. CDynamic programming
4. DBrute force

Breadth-first search (BFS) pada graf tak berbobot menemukan:

1. ALintasan terpendek pada graf yang memiliki bobot sisi negatif
2. BLintasan terpendek berdasarkan jumlah sisi dari simpul awal
3. CPohon rentang minimum
4. DUrutan topologis pada semua graf

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

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

Algoritma greedy:

1. AHanya menggunakan rekursi
2. BSelalu memberikan solusi optimal
3. CMencoba setiap solusi yang mungkin
4. DMengambil pilihan terbaik secara lokal pada setiap langkah

Algoritma Strassen mengalikan matriks memakai 7, bukan 8, perkalian rekursif blok berukuran setengah. Berapa waktu eksekusinya?

1. AΘ(n³)
2. BΘ(n² log n)
3. CΘ(n²)
4. DΘ(n^{log₂ 7}), sekitar n^2,81

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. CFloyd–Warshall
4. DAlgoritma Kruskal