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(n²)
3. CO(log n)
4. DO(1)

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

1. AKonstan
2. BLogaritmik
3. CLinear
4. DKuadratik

Berapa waktu eksekusi counting sort untuk n bilangan bulat dalam rentang 0 sampai k?

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

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

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

Berapa kompleksitas waktu algoritma Bellman–Ford pada graf dengan V simpul dan E sisi?

1. AO(V³ × E)
2. BO(V + E)
3. CO(E log V)
4. DO(V × E)

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)

Bagaimana perbandingan n! dan 2ⁿ untuk n besar?

1. A2ⁿ tumbuh lebih cepat daripada n!
2. Bn! adalah O(n²)
3. Cn! tumbuh lebih cepat daripada 2ⁿ
4. DKeduanya tumbuh dengan laju yang sama

Masalah penghentian (halting problem) menunjukkan bahwa:

1. ABeberapa program berjalan lebih cepat di komputer yang lebih cepat, sehingga berhenti atau tidaknya bergantung pada perangkat keras
2. BLoop sebaiknya dihindari
3. CSetiap program pada akhirnya akan berhenti
4. DTidak ada algoritma yang dapat memutuskan untuk setiap program dan input apakah program tersebut akan berhenti