Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu kasus terburuk insertion sort?

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

Berapa nilai log₂ 1024?

1. A12
2. B10
3. C512
4. D32

Apa yang dimaksud base case pada fungsi rekursif?

1. AKasus yang dijawab langsung tanpa melakukan pemanggilan rekursif lagi
2. BPemanggilan yang memakai memori paling banyak
3. CBaris pertama fungsi
4. DKasus dengan input terbesar, yang ditangani sebelum pemanggilan rekursif apa pun

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

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

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

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

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

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

Pernyataan manakah tentang P dan NP yang benar?

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

Perkalian Karatsuba memenuhi T(n) = 3T(n/2) + O(n). Apa hasilnya?

1. AΘ(n^{log₂ 3}), sekitar n^1,585
2. BΘ(n log n)
3. CΘ(n²)
4. DΘ(n³)