Lembar kerja Algoritma & kompleksitas dengan jawaban

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

1. ABig Omega
2. BBig Theta
3. CBig O
4. DLittle omega

Bagaimana cara kerja selection sort?

1. AMenyisipkan setiap elemen ke bagian terurut yang terus bertambah dengan menggeser
2. BBerulang kali mencari minimum dari bagian yang belum terurut lalu menukarnya ke depan
3. CBerulang kali menukar elemen bersebelahan yang urutannya salah
4. DMembagi array menjadi dua bagian lalu menggabungkannya

Suatu masalah biasanya disebut tractable jika:

1. ADapat diselesaikan dalam waktu konstan
2. BTidak memiliki solusi
3. CDapat diselesaikan dalam waktu polinomial
4. DHanya dapat diselesaikan dengan mencoba setiap kemungkinan

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

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

Kompleksitas waktu Fibonacci rekursif naif (fib(n) = fib(n−1) + fib(n−2)) adalah:

1. AKonstan
2. BLogaritmik
3. CLinear
4. DEksponensial

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

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

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

1. AMengurutkan input sebelum menjalankan quicksort
2. BMemilih pivot secara acak seragam
3. CSelalu memilih elemen pertama
4. DMenggunakan rekursi hanya pada sisi kiri

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