Lembar kerja Algoritma & kompleksitas dengan jawaban

Algoritma pengurutan mana yang memilih pivot dan mempartisi array menjadi elemen yang lebih kecil dan lebih besar?

1. AInsertion sort
2. BMerge sort
3. CBubble sort
4. DQuicksort

Berapa kompleksitas waktu kasus terbaik insertion sort, pada array yang sudah terurut?

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

Berapa nilai log₂ 1024?

1. A32
2. B10
3. C512
4. D12

Anda mengurutkan array berisi n elemen sekali, lalu menjawab k kueri keanggotaan dengan binary search. Berapa total biayanya?

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

Berapa kompleksitas waktu menghitung bilangan Fibonacci ke-n dengan tabel bottom-up?

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

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

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

Pernyataan manakah tentang P dan NP yang benar?

1. ASetiap masalah di P juga termasuk dalam NP
2. BTelah dibuktikan bahwa P ≠ NP
3. CMasalah NP tidak dapat diverifikasi dengan cepat
4. DNP berarti "not polynomial"

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

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