Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa Big O dari 3n² + 5n + 2?

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

Apa yang dimaksud base case pada fungsi rekursif?

1. AKasus dengan input terbesar, yang ditangani sebelum pemanggilan rekursif apa pun
2. BBaris pertama fungsi
3. CKasus yang dijawab langsung tanpa melakukan pemanggilan rekursif lagi
4. DPemanggilan yang memakai memori paling banyak

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

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

Berapa kompleksitas waktu algoritma dynamic programming standar untuk longest common subsequence dari string dengan panjang m dan n?

1. AO(mn)
2. BO(m + n)
3. CO(2^m+n)
4. DO(mn log n)

Berapa banyak ruang stack yang dipakai fungsi faktorial rekursif sederhana fact(n) = n × fact(n − 1)?

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

Anda mengurutkan array berisi n elemen sekali, lalu menjawab k kueri keanggotaan dengan binary search. Berapa total biayanya?

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

Bagaimana perbandingan n! dan 2ⁿ untuk n besar?

1. AKeduanya tumbuh dengan laju yang sama
2. Bn! tumbuh lebih cepat daripada 2ⁿ
3. C2ⁿ tumbuh lebih cepat daripada n!
4. Dn! adalah O(n²)

Berapa waktu eksekusi algoritma Dijkstra dengan binary heap pada graf dengan V simpul dan E sisi?

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