Latihan Soal Notasi Big O

Daftar soal tanpa kunci jawaban. Kerjakan di atas untuk melihat pembahasan.

1. Sebuah algoritma membutuhkan $3n^2 + 5n + 2$ langkah. Berapa kompleksitasnya dalam notasi Big O?

   1. $O(n)$

   2. $O(n^2)$

   3. $O(3n^2 + 5n)$

   4. $O(1)$

2. Berapa kompleksitas waktu fungsi berikut jika $n$ adalah panjang data?

   def ringkas(data):
       total = 0
       for x in data:
           total += x
       terbesar = data[0]
       for x in data:
           if x > terbesar:
               terbesar = x
       return total, terbesar
   

   1. $O(n)$

   2. $O(n^2)$

   3. $O(2^n)$

   4. $O(\log n)$

3. Algoritma $O(n^2)$ butuh sekitar 2 detik untuk $n = 1.000$. Jika $n$ menjadi 2.000 pada komputer yang sama, perkiraan waktunya berapa?

   1. 2 detik

   2. 4 detik

   3. 16 detik

   4. 8 detik

4. Algoritma mana yang memiliki kompleksitas waktu terburuk $O(\log n)$?

   1. Pencarian linear pada list acak

   2. Binary search pada list yang sudah terurut

   3. Dua perulangan bersarang sepanjang n

   4. Menjumlahkan semua elemen list

5. Program mencari $m$ nama di daftar berisi $n$ nama. Daftar diubah sekali menjadi set, lalu setiap nama diperiksa dengan in. Berapa kompleksitas rata-ratanya?

   1. $O(mn)$

   2. $O(m)$

   3. $O(n + m)$

   4. $O(n^2)$