Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang dimaksud base case pada fungsi rekursif?

1. APemanggilan yang memakai memori paling banyak
2. BKasus dengan input terbesar, yang ditangani sebelum pemanggilan rekursif apa pun
3. CBaris pertama fungsi
4. DKasus yang dijawab langsung tanpa melakukan pemanggilan rekursif lagi

Algoritma O(n) memerlukan 3 detik untuk n = 1 juta. Kira-kira berapa lama untuk n = 2 juta?

1. A12 detik
2. B9 detik
3. C6 detik
4. D3 detik

Kelas kompleksitas manakah yang tumbuh paling cepat untuk n yang besar?

1. AO(n³)
2. BO(n log 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

Pemrograman dinamis (dynamic programming) berguna ketika suatu masalah memiliki:

1. AHanya input acak
2. BSatu loop saja
3. CTidak ada submasalah sama sekali, sehingga dapat diselesaikan dalam satu langkah
4. DSubmasalah yang tumpang tindih dan substruktur optimal

Batas bawah untuk pengurutan berbasis perbandingan pada kasus terburuk adalah:

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

Mengapa algoritma Dijkstra dapat memberikan hasil yang salah ketika sebagian bobot sisi negatif?

1. AAlgoritma itu masuk ke loop tak hingga pada setiap sisi negatif
2. BBilangan negatif tidak dapat disimpan dalam priority queue
3. CAlgoritma itu hanya bekerja pada graf tak berarah
4. DSimpul ditetapkan final saat diekstraksi, tetapi sisi negatif berikutnya masih dapat memberinya lintasan yang lebih pendek

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

1. AMenggunakan rekursi hanya pada sisi kiri
2. BSelalu memilih elemen pertama
3. CMemilih pivot secara acak seragam
4. DMengurutkan input sebelum menjalankan quicksort