Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu binary search pada array yang sudah terurut?

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

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

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

Berapa kompleksitas waktu untuk mencari nilai terbesar dalam array tidak terurut berisi n bilangan?

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

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

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

Pada activity selection problem, aturan greedy mana yang selalu menghasilkan jumlah maksimum aktivitas yang tidak saling tumpang tindih?

1. APilih aktivitas yang selesai paling awal, lalu ulangi dengan aktivitas yang kompatibel
2. BPilih aktivitas yang dimulai paling awal
3. CPilih aktivitas terpendek terlebih dahulu
4. DPilih aktivitas dengan tumpang tindih paling sedikit terlebih dahulu, lalu ulangi dengan aktivitas yang kompatibel

Berapa kompleksitas waktu teramortisasi (amortised) untuk menambahkan elemen ke array dinamis yang menggandakan kapasitasnya ketika penuh?

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

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. CKarena algoritmanya bersifat acak (randomised) dan waktu eksekusinya berbeda untuk setiap input
4. DW adalah nilai numerik, sehingga waktunya eksponensial terhadap jumlah bit yang diperlukan untuk menuliskan W

Berapa biaya amortisasi menaikkan (increment) penghitung biner, mengingat satu increment dapat membalik banyak bit?

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