Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

Pertumbuhan O(2ⁿ) disebut apa?

1. APolinomial
2. BLinear
3. CEksponensial
4. DLogaritmik

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

1. Ao (little o)
2. BΩ (Big Omega)
3. CΘ (Big Theta)
4. DO (Big O)

Apakah benar mengatakan bahwa algoritma O(n²) juga O(n³)?

1. AYa, karena Big O adalah batas atas dan n² tidak tumbuh lebih cepat daripada n³
2. BTidak, karena n³ lebih kecil daripada n² untuk n besar
3. CYa, tetapi hanya jika n lebih kecil dari 100
4. DTidak, karena Big O harus selalu menyatakan laju pertumbuhan yang tepat dari fungsi itu

Bagaimana algoritma Prim membangun minimum spanning tree?

1. AMengurutkan semua sisi berdasarkan bobot dan menambahkan masing-masing kecuali jika membentuk siklus dalam hutan
2. BMenghapus sisi termahal sampai tidak ada siklus tersisa
3. CMenjalankan breadth-first search dan menyimpan pohon BFS
4. DMenumbuhkan satu pohon dari simpul awal, setiap kali menambahkan sisi termurah yang keluar dari pohon

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

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

Masalah knapsack 0/1 yang diselesaikan dengan pemrograman dinamis memerlukan waktu O(nW). Mengapa ini disebut pseudo-polinomial?

1. AKarena n selalu kecil
2. BKarena algoritma ini hanya berlaku untuk W = 0
3. CW adalah nilai numerik, sehingga waktunya eksponensial terhadap jumlah bit yang diperlukan untuk menuliskan W
4. DKarena algoritmanya bersifat acak (randomised) dan waktu eksekusinya berbeda untuk setiap input

Dengan teorema master, T(n) = 8T(n/2) + O(n²) memiliki solusi:

1. AΘ(n³)
2. BΘ(n log n)
3. CΘ(n²)
4. DΘ(n² log n)