Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa syarat binary search terhadap inputnya?

1. AArray tidak boleh berisi lebih dari 1000 elemen
2. BArray hanya boleh berisi bilangan positif
3. CPanjang array harus pangkat dua
4. DArray harus terurut

Notasi manakah yang menyatakan batas atas (upper bound) pertumbuhan?

1. ALittle omega
2. BBig Omega
3. CBig Theta
4. DBig O

Apa yang dimaksud dengan memoisasi?

1. AMenulis komentar di samping setiap baris kode
2. BMenyimpan hasil pemanggilan fungsi agar pemanggilan berulang dijawab dari memori
3. CMembebaskan memori setelah fungsi selesai
4. DMengubah rekursi menjadi loop yang setara secara otomatis sehingga call stack tidak diperlukan

Berapa banyak tingkat rekursi merge sort untuk array berisi n elemen?

1. ASekitar log₂ n
2. BSekitar n / 2
3. CSekitar n
4. DSekitar √n

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

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

Berapa banyak ruang stack yang dipakai fungsi faktorial rekursif sederhana fact(n) = n × fact(n − 1)?

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

Dengan teorema master, T(n) = 8T(n/2) + O(n²) memiliki solusi:

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

Pernyataan mana tentang notasi little-o yang benar?

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