Lembar kerja Algoritma & kompleksitas dengan jawaban

Kelas kompleksitas manakah yang tumbuh paling cepat untuk n yang besar?

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

Berapa nilai log₂ 1024?

1. A32
2. B512
3. C10
4. D12

Apa yang dimaksud dengan algoritma?

1. ABahasa pemrograman yang dirancang untuk menulis rumus matematika
2. BSetiap program komputer yang memiliki antarmuka grafis
3. CStruktur data yang menyimpan bilangan
4. DUrutan langkah yang terdefinisi dengan baik dan berhingga untuk menyelesaikan suatu masalah

Mengapa banyak rutin pengurutan pustaka beralih ke insertion sort untuk subarray yang sangat kecil?

1. AAlgoritma rekursif tidak dapat menangani array di bawah 10 elemen
2. BInsertion sort memiliki overhead kecil dan cepat pada input kecil atau hampir terurut
3. CInsertion sort adalah O(n log n) pada kasus terburuk
4. DInsertion sort memakai memori lebih sedikit daripada algoritma pengurutan lain untuk input besar

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

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

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

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

Apa akibatnya jika seseorang menemukan algoritma waktu polinomial untuk satu masalah NP-complete?

1. ASemua algoritma berwaktu eksponensial seketika berjalan dalam waktu linear
2. BSetiap masalah di NP dapat diselesaikan dalam waktu polinomial, sehingga P = NP
3. CHanya masalah itu yang pindah ke P
4. DHalting problem menjadi decidable

Berapa biaya amortisasi menaikkan (increment) penghitung biner, mengingat satu increment dapat membalik banyak bit?

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