Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

Apa yang dimaksud dengan algoritma brute force?

1. AAlgoritma yang menebak jawaban secara acak
2. BAlgoritma yang mencoba semua kandidat solusi yang mungkin
3. CAlgoritma yang selalu memakai rekursi
4. DAlgoritma yang berjalan di banyak prosesor

Berapa kompleksitas waktu binary search pada array yang sudah terurut?

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

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

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

Pemrograman dinamis (dynamic programming) berguna ketika suatu masalah memiliki:

1. ASubmasalah yang tumpang tindih dan substruktur optimal
2. BHanya input acak
3. CTidak ada submasalah sama sekali, sehingga dapat diselesaikan dalam satu langkah
4. DSatu loop saja

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

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

Mengapa pencarian rata-rata pada tabel hash adalah O(1) tetapi kasus terburuknya O(n)?

1. AKunci harus diurutkan terlebih dahulu
2. BAkses array memerlukan O(n)
3. CBanyak kunci dapat bertabrakan (collision) di bucket yang sama
4. DFungsi hash lambat

Pernyataan manakah tentang P dan NP yang benar?

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