Lembar kerja Algoritma & kompleksitas dengan jawaban

Notasi manakah yang menyatakan batas atas (upper bound) pertumbuhan?

1. ALittle omega
2. BBig Theta
3. CBig O
4. DBig Omega

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

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

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

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

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

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

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

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

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

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

Apakah 2²ⁿ termasuk O(2ⁿ)?

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

Untuk menunjukkan bahwa masalah baru X adalah NP-hard, apa yang harus Anda lakukan?

1. AMereduksi X ke masalah NP-hard yang sudah dikenal dalam waktu polinomial
2. BMereduksi masalah NP-hard yang sudah dikenal ke X dalam waktu polinomial
3. CMenunjukkan bahwa X tidak memiliki algoritma polinomial untuk input kecil
4. DMenunjukkan bahwa X dapat diverifikasi dalam waktu polinomial