Lembar kerja Algoritma & kompleksitas dengan jawaban

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

1. ABig O
2. BBig Omega
3. CBig Theta
4. DLittle omega

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

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

Apa yang dimaksud dengan rekursi?

1. ASebuah metode pengurutan
2. BLoop yang tidak pernah berakhir
3. CSejenis struktur data
4. DFungsi yang memanggil dirinya sendiri dengan input yang lebih kecil

Mengapa dynamic programming tidak benar-benar mempercepat merge sort?

1. ADynamic programming hanya bekerja pada masalah graf, bukan pada array
2. BSubmasalahnya tidak tumpang tindih, sehingga tidak ada yang dapat dipakai ulang
3. CMerge sort tidak memiliki struktur rekursif
4. DMerge sort sudah O(n)

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

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

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

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

Suatu masalah disebut NP-complete jika masalah tersebut:

1. ATermasuk dalam NP dan setiap masalah NP dapat direduksi ke masalah tersebut dalam waktu polinomial
2. BBerada di luar NP tetapi lebih sulit daripada semua masalah NP, seperti halting problem
3. CTidak mungkin diselesaikan
4. DDapat diselesaikan 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³)