Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

Apa tiga langkah algoritma divide and conquer?

1. AUrutkan, cari, kembalikan
2. BTebak, periksa, ulangi
3. CDivide, conquer, combine (bagi, taklukkan, gabungkan)
4. DBaca, hitung, tulis

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

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

Berapa kompleksitas waktu menghitung bilangan Fibonacci ke-n dengan tabel bottom-up?

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

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

1. AO(2ⁿ)
2. BO(n)
3. CO(log 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 500,000
2. BSekitar 100
3. CSekitar 20
4. DSekitar 1,000

Pernyataan mana tentang notasi little-o yang benar?

1. An = o(n²), tetapi n bukan o(n)
2. B2n = o(n), karena 2n tumbuh lambat
3. Cn = o(n), karena setiap fungsi adalah little-o dari dirinya sendiri
4. Dn² = o(n)

Mengapa binary search tidak menghasilkan waktu O(log n) pada singly linked list?

1. APerbandingan pada node linked list lebih lambat
2. BBinary search memerlukan setidaknya dua kali lipat memori
3. CLinked list tidak dapat diurutkan
4. DMencapai elemen tengah memerlukan O(n) langkah, karena tidak ada akses indeks langsung