Lembar kerja Algoritma & kompleksitas dengan jawaban

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

1. A6 detik
2. B12 detik
3. C9 detik
4. D3 detik

Berapa waktu eksekusi counting sort untuk n bilangan bulat dalam rentang 0 sampai k?

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

Berapa kompleksitas waktu kasus terbaik insertion sort, pada array yang sudah terurut?

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

Quicksort selalu memakai elemen pertama sebagai pivot. Pada input mana algoritma ini menunjukkan perilaku kasus terburuknya?

1. AArray yang semua elemennya berbeda
2. BArray dengan panjang 2
3. CArray dalam urutan acak
4. DArray yang sudah terurut

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

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

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

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

Mengapa setiap pencarian berbasis perbandingan dalam array terurut memerlukan Ω(log n) perbandingan pada kasus terburuk?

1. ABinary search adalah satu-satunya algoritma yang mungkin, dan memerlukan log₂ n perbandingan
2. BSetiap perbandingan memerlukan waktu logaritmik
3. CPohon keputusan dengan n kemungkinan hasil harus memiliki kedalaman setidaknya log₂ n
4. DSetiap elemen harus dibandingkan setidaknya sekali

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

1. ASelalu memilih elemen pertama
2. BMengurutkan input sebelum menjalankan quicksort
3. CMemilih pivot secara acak seragam
4. DMenggunakan rekursi hanya pada sisi kiri