Lembar kerja Algoritma & kompleksitas dengan jawaban

Algoritma dengan dua loop bersarang, yang masing-masing berjalan n kali, biasanya memiliki kompleksitas apa?

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

Berapa waktu eksekusi counting sort untuk n bilangan bulat dalam rentang 0 sampai k?

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

Berapa kompleksitas waktu kasus terburuk merge sort?

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

Berapa kompleksitas waktu kasus terburuk quicksort?

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

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

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

Pernyataan mana tentang fungsi rekursif tanpa base case yang dapat dicapai yang benar?

1. AFungsi itu berjalan dalam waktu O(1)
2. BKompiler selalu mengubahnya menjadi loop yang berakhir dengan aman
3. CFungsi itu otomatis mengembalikan 0
4. DFungsi itu terus memanggil dirinya sendiri sampai call stack meluap (overflow)

Apakah 2²ⁿ termasuk O(2ⁿ)?

1. ATidak, karena 2²ⁿ = 4ⁿ dan 4ⁿ / 2ⁿ = 2ⁿ tumbuh tanpa batas
2. BTidak, karena 2²ⁿ tumbuh lebih lambat daripada 2ⁿ
3. CYa, karena faktor konstan pada pangkat selalu diabaikan dalam Big O
4. DYa, karena keduanya eksponensial

Apa yang ditetapkan oleh teorema Cook–Levin?

1. AP tidak sama dengan NP
2. BSetiap masalah NP dapat diselesaikan dalam waktu eksponensial
3. CHalting problem tidak dapat diputuskan (undecidable)
4. DBoolean satisfiability problem (SAT) adalah NP-complete