Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu kasus terburuk merge sort?

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

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)

Apa yang dimaksud dengan memoisasi?

1. AMenulis komentar di samping setiap baris kode
2. BMembebaskan memori setelah fungsi selesai
3. CMengubah rekursi menjadi loop yang setara secara otomatis sehingga call stack tidak diperlukan
4. DMenyimpan hasil pemanggilan fungsi agar pemanggilan berulang dijawab dari memori

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

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

Relasi rekurens T(n) = 2T(n/2) + O(n) memiliki solusi:

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

Berapa banyak tingkat rekursi merge sort untuk array berisi n elemen?

1. ASekitar n
2. BSekitar √n
3. CSekitar n / 2
4. DSekitar log₂ n

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

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

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

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