Lembar kerja Algoritma & kompleksitas dengan jawaban

Waktu eksekusi suatu algoritma adalah O(n). Pertumbuhan ini disebut apa?

1. ALinear
2. BKonstan
3. CKuadratik
4. DLogaritmik

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

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

Pertumbuhan O(2ⁿ) disebut apa?

1. ALogaritmik
2. BPolinomial
3. CEksponensial
4. DLinear

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

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

Batas bawah untuk pengurutan berbasis perbandingan pada kasus terburuk adalah:

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

Bagaimana algoritma Prim membangun minimum spanning tree?

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

Apa akibatnya jika seseorang menemukan algoritma waktu polinomial untuk satu masalah NP-complete?

1. AHalting problem menjadi decidable
2. BSetiap masalah di NP dapat diselesaikan dalam waktu polinomial, sehingga P = NP
3. CHanya masalah itu yang pindah ke P
4. DSemua algoritma berwaktu eksponensial seketika berjalan dalam waktu linear

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

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