Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

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 diharapkan pada input acak berukuran n
4. DWaktu yang diperlukan pada komputer yang lambat

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

1. AKonstan
2. BLogaritmik
3. CLinear
4. DKuadratik

Dalam array terurut, Anda mencari dua elemen yang jumlahnya sama dengan target dengan menggerakkan satu pointer dari masing-masing ujung ke dalam. Berapa kompleksitas waktunya?

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

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

1. AO(n)
2. BO(2ⁿ)
3. CO(n log 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 dengan tumpang tindih paling sedikit terlebih dahulu, lalu ulangi dengan aktivitas yang kompatibel
4. DPilih aktivitas terpendek terlebih dahulu

Pengurutan topologis hanya mungkin dilakukan untuk:

1. AGraf dengan bobot negatif
2. BGraf lengkap
3. CGraf berarah asiklik (DAG)
4. DGraf tak berarah

Teknik manakah yang memberikan waktu eksekusi harapan (expected) O(n log n) untuk quicksort pada input apa pun?

1. ASelalu memilih elemen pertama
2. BMengurutkan input sebelum menjalankan quicksort
3. CMemilih pivot secara acak seragam
4. DMenggunakan rekursi hanya pada sisi kiri