Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

Kelas kompleksitas manakah yang tumbuh paling cepat untuk n yang besar?

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

Apa artinya jika suatu operasi berjalan dalam waktu O(1)?

1. AHanya dapat dijalankan sekali
2. BMemproses tepat satu elemen per detik waktu eksekusi
3. CWaktu eksekusinya tidak bertambah seiring ukuran input
4. DSelalu memerlukan tepat satu detik

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

1. ALogaritma selalu dibulatkan menjadi bilangan bulat
2. BLogaritma dengan basis berbeda hanya berbeda faktor konstan
3. CSemua logaritma dalam ilmu komputer berbasis 10, sehingga basisnya tersirat
4. DBasis hanya berpengaruh untuk n kecil

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

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

Berapa kompleksitas waktu dari: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Rekurens T(n) = 2T(n/2) + n log n menghasilkan apa?

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

Berapa biaya amortisasi menaikkan (increment) penghitung biner, mengingat satu increment dapat membalik banyak bit?

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