Lembar kerja Algoritma & kompleksitas dengan jawaban

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

1. ALogaritmik
2. BKonstan
3. CLinear
4. DKuadratik

Notasi manakah yang menyatakan batas atas (upper bound) pertumbuhan?

1. ABig Omega
2. BLittle omega
3. CBig Theta
4. DBig O

Sebuah loop dimulai dengan i = 1 dan menggandakan i setiap iterasi sampai i > n. Berapa kali loop itu berjalan?

1. ASekitar log₂ n
2. BSekitar n²
3. CSekitar n
4. DSekitar n / 2

Berapa kompleksitas waktu mengalikan dua matriks n × n dengan triple loop standar?

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

Kira-kira berapa perbandingan yang diperlukan binary search pada kasus terburuk untuk array terurut berisi 1,000,000 elemen?

1. ASekitar 20
2. BSekitar 500,000
3. CSekitar 100
4. DSekitar 1,000

Berapa kompleksitas waktu dari: for i = 1 to n: for j = 1 to i: lakukan kerja O(1)?

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

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 algoritma ini hanya berlaku untuk W = 0
3. CKarena n selalu kecil
4. DKarena algoritmanya bersifat acak (randomised) dan waktu eksekusinya berbeda untuk setiap input

Perkalian Karatsuba memenuhi T(n) = 3T(n/2) + O(n). Apa hasilnya?

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