Lembar kerja Algoritma & kompleksitas dengan jawaban

Notasi manakah yang menyatakan batas atas (upper bound) pertumbuhan?

1. ABig O
2. BLittle omega
3. CBig Theta
4. DBig Omega

Bagaimana cara kerja selection sort?

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

Berapa kompleksitas waktu kasus terburuk insertion sort?

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

Breadth-first search (BFS) pada graf tak berbobot menemukan:

1. ALintasan terpendek pada graf yang memiliki bobot sisi negatif
2. BPohon rentang minimum
3. CLintasan terpendek berdasarkan jumlah sisi dari simpul awal
4. DUrutan topologis pada semua graf

Berapa kompleksitas waktu teramortisasi (amortised) untuk menambahkan elemen ke array dinamis yang menggandakan kapasitasnya ketika penuh?

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

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

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

Batas mana yang benar untuk log(n!)?

1. AΘ(n²)
2. BΘ(log n)
3. CΘ(n)
4. DΘ(n log n)

Pernyataan manakah tentang P dan NP yang benar?

1. AMasalah NP tidak dapat diverifikasi dengan cepat
2. BSetiap masalah di P juga termasuk dalam NP
3. CNP berarti "not polynomial"
4. DTelah dibuktikan bahwa P ≠ NP