Lembar kerja Algoritma & kompleksitas dengan jawaban

Waktu eksekusi suatu algoritma adalah O(n). Pertumbuhan ini disebut apa?

1. AKonstan
2. BKuadratik
3. CLinear
4. DLogaritmik

Apa tiga langkah algoritma divide and conquer?

1. AUrutkan, cari, kembalikan
2. BTebak, periksa, ulangi
3. CDivide, conquer, combine (bagi, taklukkan, gabungkan)
4. DBaca, hitung, tulis

Manakah yang tumbuh paling lambat ketika n menjadi besar?

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

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(2ⁿ)
4. DO(n²)

Batas bawah untuk pengurutan berbasis perbandingan pada kasus terburuk adalah:

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

Kompleksitas waktu Fibonacci rekursif naif (fib(n) = fib(n−1) + fib(n−2)) adalah:

1. ALinear
2. BEksponensial
3. CLogaritmik
4. DKonstan

Apa yang ditetapkan oleh teorema Cook–Levin?

1. AHalting problem tidak dapat diputuskan (undecidable)
2. BSetiap masalah NP dapat diselesaikan dalam waktu eksponensial
3. CP tidak sama dengan NP
4. DBoolean satisfiability problem (SAT) adalah NP-complete

Insertion sort berjalan dalam O(n) pada input terurut. Apakah ini bertentangan dengan batas bawah Ω(n log n) untuk pengurutan berbasis perbandingan?

1. ATidak, batas bawah itu berlaku untuk kasus terburuk atas semua input, bukan untuk setiap input
2. BYa, tetapi hanya untuk array yang lebih pendek dari 100
3. CTidak, karena insertion sort bukan pengurutan berbasis perbandingan
4. DYa, sehingga batas bawah itu salah