Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang digambarkan oleh waktu eksekusi kasus terburuk suatu algoritma?

1. AWaktu yang diperlukan pada input terkecil
2. BWaktu maksimum yang diperlukan atas semua input berukuran n
3. CWaktu yang diperlukan pada komputer yang lambat
4. DWaktu yang diharapkan pada input acak berukuran n

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

1. ALinear
2. BLogaritmik
3. CKonstan
4. DKuadratik

Algoritma O(n²) memerlukan 1 detik untuk n = 1000. Kira-kira berapa lama untuk n = 2000?

1. A1 detik
2. B4 detik
3. C8 detik
4. D2 detik

Berapa kompleksitas waktu algoritma dynamic programming standar untuk longest common subsequence dari string dengan panjang m dan n?

1. AO(2^m+n)
2. BO(mn)
3. CO(mn log n)
4. DO(m + n)

Relasi rekurens T(n) = 2T(n/2) + O(n) memiliki solusi:

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

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

1. AO(1)
2. BO(n²)
3. CO(log 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

Berapa biaya waktu dan ruang untuk menghitung bilangan Fibonacci ke-n dengan loop yang hanya menyimpan dua nilai terakhir?

1. AWaktu O(2ⁿ) dan ruang O(1)
2. BWaktu O(n) dan ruang O(n)
3. CWaktu O(log n) dan ruang O(n)
4. DWaktu O(n) dan ruang O(1)