Lembar kerja Algoritma & kompleksitas dengan jawaban

Sebuah loop dimulai dengan i = 1 dan menggandakan i setiap iterasi sampai i > n. Berapa kali loop itu berjalan?

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

Apa yang dimaksud dengan rekursi?

1. ASejenis struktur data
2. BLoop yang tidak pernah berakhir
3. CSebuah metode pengurutan
4. DFungsi yang memanggil dirinya sendiri dengan input yang lebih kecil

Manakah dari waktu eksekusi berikut yang polinomial?

1. AO(n³)
2. BO(n!)
3. CO(nⁿ)
4. DO(2ⁿ)

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

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

Algoritma pengurutan manakah yang stabil (stable)?

1. AQuicksort (versi in-place yang umum)
2. BSelection sort (versi yang umum)
3. CHeap sort
4. DMerge sort

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

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

Apakah 2²ⁿ termasuk O(2ⁿ)?

1. ATidak, karena 2²ⁿ = 4ⁿ dan 4ⁿ / 2ⁿ = 2ⁿ tumbuh tanpa batas
2. BYa, karena faktor konstan pada pangkat selalu diabaikan dalam Big O
3. CTidak, karena 2²ⁿ tumbuh lebih lambat daripada 2ⁿ
4. DYa, karena keduanya eksponensial

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

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