Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu kasus terburuk merge sort?

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

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

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

Mengakses elemen array berdasarkan indeks memerlukan waktu:

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

Berapa waktu eksekusi LSD radix sort pada n bilangan bulat dengan d digit dalam basis k?

1. AO(d(n + k))
2. BO(dn log k)
3. CO(n log n)
4. DO(n²)

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

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

Sebuah fungsi menjalankan satu loop berisi n iterasi, lalu secara terpisah satu loop lain berisi n iterasi. Berapa kompleksitas waktunya?

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

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. BMenunjukkan bahwa X dapat diverifikasi dalam waktu polinomial
3. CMenunjukkan bahwa X tidak memiliki algoritma polinomial untuk input kecil
4. DMereduksi masalah NP-hard yang sudah dikenal ke X dalam waktu polinomial

Apa perbedaan antara masalah undecidable dan masalah intractable?

1. ATidak ada algoritma yang menyelesaikan masalah undecidable untuk semua input, sedangkan masalah intractable dapat diselesaikan tetapi terlalu lambat
2. BMasalah intractable tidak dapat diselesaikan oleh algoritma apa pun, sedangkan masalah undecidable hanya memerlukan waktu eksponensial
3. CMasalah undecidable berada di NP, sedangkan masalah intractable di P
4. DKeduanya berarti masalah itu sama sekali tidak memiliki algoritma