Lembar kerja Algoritma & kompleksitas dengan jawaban

Kompleksitas ruang (space complexity) mengukur:

1. AJumlah memori yang dibutuhkan algoritma seiring bertambahnya input
2. BJumlah baris kode
3. CRuang disk yang dipakai file program setelah dikompilasi
4. DUkuran fisik komputer

Apa yang digambarkan oleh waktu eksekusi kasus rata-rata?

1. AWaktu pada komputer yang paling umum
2. BNilai tengah antara waktu eksekusi kasus terbaik dan kasus terburuk
3. CWaktu untuk input dengan panjang rata-rata
4. DWaktu yang diharapkan atas distribusi input berukuran n tertentu

Berapa Big O dari 3n² + 5n + 2?

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

Kira-kira berapa perbandingan yang diperlukan binary search pada kasus terburuk untuk array terurut berisi 1,000,000 elemen?

1. ASekitar 500,000
2. BSekitar 100
3. CSekitar 1,000
4. DSekitar 20

Berapa banyak ruang stack yang dipakai fungsi faktorial rekursif sederhana fact(n) = n × fact(n − 1)?

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

Apakah benar mengatakan bahwa algoritma O(n²) juga O(n³)?

1. ATidak, karena n³ lebih kecil daripada n² untuk n besar
2. BYa, karena Big O adalah batas atas dan n² tidak tumbuh lebih cepat daripada n³
3. CTidak, karena Big O harus selalu menyatakan laju pertumbuhan yang tepat dari fungsi itu
4. DYa, tetapi hanya jika n lebih kecil dari 100

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

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

Perkalian Karatsuba memenuhi T(n) = 3T(n/2) + O(n). Apa hasilnya?

1. AΘ(n log n)
2. BΘ(n³)
3. CΘ(n²)
4. DΘ(n^{log₂ 3}), sekitar n^1,585