Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu untuk mencari nilai terbesar dalam array tidak terurut berisi n bilangan?

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

Berapa kompleksitas waktu kasus terburuk insertion sort?

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

Apa yang digambarkan oleh waktu eksekusi kasus terburuk suatu algoritma?

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

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

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

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

1. AUrutan topologis pada semua graf
2. BLintasan terpendek pada graf yang memiliki bobot sisi negatif
3. CPohon rentang minimum
4. DLintasan terpendek berdasarkan jumlah sisi dari simpul awal

Pada activity selection problem, aturan greedy mana yang selalu menghasilkan jumlah maksimum aktivitas yang tidak saling tumpang tindih?

1. APilih aktivitas yang selesai paling awal, lalu ulangi dengan aktivitas yang kompatibel
2. BPilih aktivitas terpendek terlebih dahulu
3. CPilih aktivitas yang dimulai paling awal
4. DPilih aktivitas dengan tumpang tindih paling sedikit terlebih dahulu, lalu ulangi dengan aktivitas yang kompatibel

Dengan teorema master, T(n) = 8T(n/2) + O(n²) memiliki solusi:

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

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

1. AAkses array memerlukan O(n)
2. BFungsi hash lambat
3. CKunci harus diurutkan terlebih dahulu
4. DBanyak kunci dapat bertabrakan (collision) di bucket yang sama