Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

Apa syarat binary search terhadap inputnya?

1. AArray harus terurut
2. BArray tidak boleh berisi lebih dari 1000 elemen
3. CPanjang array harus pangkat dua
4. DArray hanya boleh berisi bilangan positif

Mengakses elemen array berdasarkan indeks memerlukan waktu:

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

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

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

Batas bawah untuk pengurutan berbasis perbandingan pada kasus terburuk adalah:

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

Berapa kompleksitas waktu teramortisasi (amortised) untuk menambahkan elemen ke array dinamis yang menggandakan kapasitasnya ketika penuh?

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

Mengapa binary search tidak menghasilkan waktu O(log n) pada singly linked list?

1. ABinary search memerlukan setidaknya dua kali lipat memori
2. BPerbandingan pada node linked list lebih lambat
3. CLinked list tidak dapat diurutkan
4. DMencapai elemen tengah memerlukan O(n) langkah, karena tidak ada akses indeks langsung

Pernyataan mana tentang notasi little-o yang benar?

1. An = o(n²), tetapi n bukan o(n)
2. B2n = o(n), karena 2n tumbuh lambat
3. Cn = o(n), karena setiap fungsi adalah little-o dari dirinya sendiri
4. Dn² = o(n)