Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu depth-first search pada graf yang disimpan sebagai adjacency list?

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

Berapa kompleksitas waktu kasus terbaik insertion sort, pada array yang sudah terurut?

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

Apa yang digambarkan oleh waktu eksekusi kasus rata-rata?

1. AWaktu pada komputer yang paling umum
2. BWaktu untuk input dengan panjang rata-rata
3. CNilai tengah antara waktu eksekusi kasus terbaik dan kasus terburuk
4. DWaktu yang diharapkan atas distribusi input berukuran n tertentu

Pernyataan mana tentang fungsi rekursif tanpa base case yang dapat dicapai yang benar?

1. AKompiler selalu mengubahnya menjadi loop yang berakhir dengan aman
2. BFungsi itu berjalan dalam waktu O(1)
3. CFungsi itu otomatis mengembalikan 0
4. DFungsi itu terus memanggil dirinya sendiri sampai call stack meluap (overflow)

Mengapa basis logaritma biasanya tidak dituliskan dalam Big O, seperti pada O(log n)?

1. ABasis hanya berpengaruh untuk n kecil
2. BSemua logaritma dalam ilmu komputer berbasis 10, sehingga basisnya tersirat
3. CLogaritma dengan basis berbeda hanya berbeda faktor konstan
4. DLogaritma selalu dibulatkan menjadi bilangan bulat

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

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

Apa yang ditetapkan oleh teorema Cook–Levin?

1. AP tidak sama dengan NP
2. BHalting problem tidak dapat diputuskan (undecidable)
3. CBoolean satisfiability problem (SAT) adalah NP-complete
4. DSetiap masalah NP dapat diselesaikan dalam waktu eksponensial

Algoritma dynamic programming Held–Karp menyelesaikan travelling salesman problem secara eksak. Berapa waktu eksekusinya untuk n kota?

1. AO(n!)
2. BO(2^n²)
3. CO(n³)
4. DO(n² 2ⁿ)