Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

Apa yang digambarkan oleh waktu eksekusi kasus rata-rata?

1. AWaktu yang diharapkan atas distribusi input berukuran n tertentu
2. BWaktu untuk input dengan panjang rata-rata
3. CWaktu pada komputer yang paling umum
4. DNilai tengah antara waktu eksekusi kasus terbaik dan kasus terburuk

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

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

Sebuah fungsi menjalankan satu loop berisi n iterasi, lalu secara terpisah satu loop lain berisi n iterasi. Berapa kompleksitas waktunya?

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

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)

Berapa kompleksitas waktu algoritma Bellman–Ford pada graf dengan V simpul dan E sisi?

1. AO(V + E)
2. BO(V × E)
3. CO(V³ × E)
4. DO(E log V)

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

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

Definisi kelas NP manakah yang benar?

1. AMasalah keputusan yang jawaban "ya"-nya dapat diverifikasi dalam waktu polinomial jika diberi sertifikat
2. BMasalah yang tidak dapat diselesaikan algoritma apa pun
3. CMasalah yang tidak dapat diselesaikan dalam waktu polinomial
4. DMasalah yang tidak polinomial