Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu kasus terburuk merge sort?

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

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

1. A9 detik
2. B12 detik
3. C6 detik
4. D3 detik

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

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

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

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

Berapa waktu eksekusi LSD radix sort pada n bilangan bulat dengan d digit dalam basis k?

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

Batas bawah untuk pengurutan berbasis perbandingan pada kasus terburuk adalah:

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

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

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

Berapa kompleksitas waktu membangun binary heap dari n elemen tidak terurut dengan metode bottom-up?

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