Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

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

Berapa kompleksitas waktu untuk mencari nilai terbesar dalam array tidak terurut berisi n bilangan?

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

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

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

Apa artinya suatu masalah memiliki optimal substructure?

1. AMasalah itu memiliki tepat satu solusi optimal, yang dimiliki bersama oleh setiap submasalah
2. BMasalah itu dapat diselesaikan dalam waktu konstan
3. CSolusi optimal dapat dibangun dari solusi optimal submasalahnya
4. DSetiap submasalah memiliki ukuran yang sama

Berapa kompleksitas waktu mengalikan dua matriks n × n dengan triple loop standar?

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

Batas mana yang benar untuk log(n!)?

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

Algoritma Strassen mengalikan matriks memakai 7, bukan 8, perkalian rekursif blok berukuran setengah. Berapa waktu eksekusinya?

1. AΘ(n^{log₂ 7}), sekitar n^2,81
2. BΘ(n²)
3. CΘ(n³)
4. DΘ(n² log n)