Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang digambarkan oleh waktu eksekusi kasus terburuk suatu algoritma?

1. AWaktu maksimum yang diperlukan atas semua input berukuran n
2. BWaktu yang diperlukan pada komputer yang lambat
3. CWaktu yang diperlukan pada input terkecil
4. DWaktu yang diharapkan pada input acak berukuran n

Apa artinya jika suatu operasi berjalan dalam waktu O(1)?

1. AMemproses tepat satu elemen per detik waktu eksekusi
2. BWaktu eksekusinya tidak bertambah seiring ukuran input
3. CHanya dapat dijalankan sekali
4. DSelalu memerlukan tepat satu detik

Sebuah loop dimulai dengan i = 1 dan menggandakan i setiap iterasi sampai i > n. Berapa kali loop itu berjalan?

1. ASekitar n / 2
2. BSekitar log₂ n
3. CSekitar n
4. DSekitar n²

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

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

Berapa banyak tingkat rekursi merge sort untuk array berisi n elemen?

1. ASekitar n
2. BSekitar log₂ n
3. CSekitar √n
4. DSekitar n / 2

Mengapa dynamic programming tidak benar-benar mempercepat merge sort?

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

Pengurutan topologis hanya mungkin dilakukan untuk:

1. AGraf lengkap
2. BGraf dengan bobot negatif
3. CGraf berarah asiklik (DAG)
4. DGraf tak berarah

Mengambil kedua titik ujung dari setiap sisi dalam maximal matching menghasilkan vertex cover. Seberapa baik cover ini?

1. ASelalu merupakan minimum vertex cover
2. BPaling banyak log n kali minimum
3. CKualitasnya tidak diketahui dibandingkan optimum
4. DPaling banyak dua kali ukuran minimum vertex cover