Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu untuk mencari nilai terbesar dalam array tidak terurut berisi n bilangan?

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

Notasi manakah yang menyatakan batas bawah (lower bound) pertumbuhan?

1. AO (Big O)
2. Bo (little o)
3. CΘ (Big Theta)
4. DΩ (Big Omega)

Apa artinya jika suatu operasi berjalan dalam waktu O(1)?

1. AWaktu eksekusinya tidak bertambah seiring ukuran input
2. BHanya dapat dijalankan sekali
3. CSelalu memerlukan tepat satu detik
4. DMemproses tepat satu elemen per detik waktu eksekusi

Mengapa basis logaritma biasanya tidak dituliskan dalam Big O, seperti pada O(log n)?

1. ASemua logaritma dalam ilmu komputer berbasis 10, sehingga basisnya tersirat
2. BLogaritma dengan basis berbeda hanya berbeda faktor konstan
3. CLogaritma selalu dibulatkan menjadi bilangan bulat
4. DBasis hanya berpengaruh untuk n kecil

Algoritma greedy:

1. ASelalu memberikan solusi optimal
2. BHanya menggunakan rekursi
3. CMencoba setiap solusi yang mungkin
4. DMengambil pilihan terbaik secara lokal pada setiap langkah

Berapa kompleksitas waktu algoritma Bellman–Ford pada graf dengan V simpul dan E sisi?

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

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

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

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

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