Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

Berapa kompleksitas waktu binary search pada array yang sudah terurut?

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

Bagaimana cara kerja selection sort?

1. AMenyisipkan setiap elemen ke bagian terurut yang terus bertambah dengan menggeser
2. BMembagi array menjadi dua bagian lalu menggabungkannya
3. CBerulang kali mencari minimum dari bagian yang belum terurut lalu menukarnya ke depan
4. DBerulang kali menukar elemen bersebelahan yang urutannya salah

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

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

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

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

Berapa kompleksitas waktu mengalikan dua matriks n × n dengan triple loop standar?

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

Algoritma dynamic programming Held–Karp menyelesaikan travelling salesman problem secara eksak. Berapa waktu eksekusinya untuk n kota?

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

Apa yang ditetapkan oleh teorema Cook–Levin?

1. ABoolean satisfiability problem (SAT) adalah NP-complete
2. BHalting problem tidak dapat diputuskan (undecidable)
3. CSetiap masalah NP dapat diselesaikan dalam waktu eksponensial
4. DP tidak sama dengan NP