Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa syarat binary search terhadap inputnya?

1. AArray harus terurut
2. BArray hanya boleh berisi bilangan positif
3. CArray tidak boleh berisi lebih dari 1000 elemen
4. DPanjang array harus pangkat dua

Strategi desain apa yang digunakan merge sort?

1. ADynamic programming
2. BDivide and conquer (bagi dan taklukkan)
3. CBrute force
4. DPilihan greedy

Berapa kompleksitas waktu linear search pada array tidak terurut berisi n elemen (kasus terburuk)?

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

Berapa kompleksitas waktu kasus terburuk quicksort?

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

Berapa kompleksitas waktu algoritma Bellman–Ford pada graf dengan V simpul dan E sisi?

1. AO(V × E)
2. BO(V³ × E)
3. CO(E log V)
4. DO(V + E)

Kira-kira berapa perbandingan yang diperlukan binary search pada kasus terburuk untuk array terurut berisi 1,000,000 elemen?

1. ASekitar 1,000
2. BSekitar 500,000
3. CSekitar 100
4. DSekitar 20

Berapa biaya amortisasi menaikkan (increment) penghitung biner, mengingat satu increment dapat membalik banyak bit?

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

Apakah 2²ⁿ termasuk O(2ⁿ)?

1. AYa, karena keduanya eksponensial
2. BTidak, karena 2²ⁿ tumbuh lebih lambat daripada 2ⁿ
3. CYa, karena faktor konstan pada pangkat selalu diabaikan dalam Big O
4. DTidak, karena 2²ⁿ = 4ⁿ dan 4ⁿ / 2ⁿ = 2ⁿ tumbuh tanpa batas