Lembar kerja Algoritma & kompleksitas dengan jawaban

Algoritma pengurutan manakah yang berulang kali menukar elemen bersebelahan yang urutannya salah?

1. AHeap sort
2. BMerge sort
3. CBubble sort
4. DQuicksort

Berapa banyak memori tambahan yang dipakai merge sort standar berbasis array?

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

Mengakses elemen array berdasarkan indeks memerlukan waktu:

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

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

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

Pernyataan mana tentang fungsi rekursif tanpa base case yang dapat dicapai yang benar?

1. AFungsi itu berjalan dalam waktu O(1)
2. BFungsi itu terus memanggil dirinya sendiri sampai call stack meluap (overflow)
3. CKompiler selalu mengubahnya menjadi loop yang berakhir dengan aman
4. DFungsi itu otomatis mengembalikan 0

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

1. AEksponensial
2. BLinear
3. CLogaritmik
4. DKonstan

Berapa waktu eksekusi algoritma Dijkstra dengan binary heap pada graf dengan V simpul dan E sisi?

1. AO(V³)
2. BO(V + E)
3. CO(V × E)
4. DO((V + E) log V)

Insertion sort berjalan dalam O(n) pada input terurut. Apakah ini bertentangan dengan batas bawah Ω(n log n) untuk pengurutan berbasis perbandingan?

1. AYa, sehingga batas bawah itu salah
2. BTidak, batas bawah itu berlaku untuk kasus terburuk atas semua input, bukan untuk setiap input
3. CTidak, karena insertion sort bukan pengurutan berbasis perbandingan
4. DYa, tetapi hanya untuk array yang lebih pendek dari 100