Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa banyak memori tambahan yang dipakai merge sort standar berbasis array?

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

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

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

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

1. AQuicksort
2. BInsertion sort
3. CBubble sort
4. DMerge sort

Quicksort selalu memakai elemen pertama sebagai pivot. Pada input mana algoritma ini menunjukkan perilaku kasus terburuknya?

1. AArray yang sudah terurut
2. BArray dengan panjang 2
3. CArray dalam urutan acak
4. DArray yang semua elemennya berbeda

Mengapa dynamic programming tidak benar-benar mempercepat merge sort?

1. ASubmasalahnya tidak tumpang tindih, sehingga tidak ada yang dapat dipakai ulang
2. BMerge sort tidak memiliki struktur rekursif
3. CMerge sort sudah O(n)
4. DDynamic programming hanya bekerja pada masalah graf, bukan pada array

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

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

Pernyataan mana tentang notasi little-o yang benar?

1. An² = o(n)
2. B2n = o(n), karena 2n tumbuh lambat
3. Cn = o(n²), tetapi n bukan o(n)
4. Dn = o(n), karena setiap fungsi adalah little-o dari dirinya sendiri

Bagaimana travelling salesman problem diklasifikasikan?

1. AMasalah ini undecidable
2. BMasalah ini berada di P karena algoritma Dijkstra menyelesaikannya dengan mengunjungi setiap kota satu kali
3. CVersi keputusannya NP-complete dan versi optimasinya NP-hard
4. DVersi keputusannya di P tetapi versi optimasinya NP-complete