Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

Notasi manakah yang menyatakan batas bawah (lower bound) pertumbuhan?

1. AΩ (Big Omega)
2. BO (Big O)
3. Co (little o)
4. DΘ (Big Theta)

Kompleksitas ruang (space complexity) mengukur:

1. ARuang disk yang dipakai file program setelah dikompilasi
2. BJumlah memori yang dibutuhkan algoritma seiring bertambahnya input
3. CJumlah baris kode
4. DUkuran fisik komputer

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

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

Dalam array terurut, Anda mencari dua elemen yang jumlahnya sama dengan target dengan menggerakkan satu pointer dari masing-masing ujung ke dalam. Berapa kompleksitas waktunya?

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

Berapa kompleksitas waktu menghitung bilangan Fibonacci ke-n dengan tabel bottom-up?

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

Definisi kelas P manakah yang benar?

1. AMasalah yang dapat diselesaikan secara paralel
2. BMasalah keputusan yang dapat diselesaikan algoritma deterministik dalam waktu polinomial
3. CMasalah yang memerlukan waktu eksponensial pada setiap komputer
4. DMasalah yang solusinya dapat diperiksa tetapi tidak pernah dapat ditemukan dalam waktu polinomial

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

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