1. Pengertian Big O

Big O Notation adalah notasi yang digunakan untuk menggambarkan tingkat pertumbuhan kompleksitas suatu algoritma terhadap ukuran input.

Secara sederhana:

Big O menjawab pertanyaan: “Jika jumlah data semakin besar, seberapa cepat kebutuhan operasi algoritma bertambah?”

Misalnya kita mempunyai algoritma dengan data sebanyak n.

Jika jumlah operasi kira-kira:

n

maka:

O(n)

Jika jumlah operasinya:

n²

maka:

O(n²)

Jika jumlah operasinya:

log n

maka:

O(log n)

Jadi Big O berhubungan dengan pertumbuhan, bukan sekadar jumlah operasi pada satu ukuran data.

---

2. Mengapa Kita Membutuhkan Big O?

Bayangkan ada dua algoritma.

Algoritma A

Membutuhkan:

10n operasi

Algoritma B

Membutuhkan:

n² operasi

Jika:

n = 10

maka:

A = 10 × 10 = 100
B = 10² = 100

Terlihat sama.

Tetapi jika:

n = 1.000

maka:

A = 10 × 1.000
  = 10.000

B = 1.000²
  = 1.000.000

Perbedaannya menjadi sangat besar.

Big O membantu kita memahami perilaku algoritma ketika input membesar.

---

3. Konsep Utama: Input Size n

Dalam Big O, n biasanya digunakan untuk menunjukkan ukuran input.

Contoh:

Data = [10, 20, 30, 40, 50]

Jumlah data:

n = 5

Jika terdapat 1.000 data:

n = 1.000

Jika terdapat 1.000.000 data:

n = 1.000.000

Jadi:

n = ukuran masalah

Penting: n tidak selalu berarti jumlah elemen list.

Tergantung masalahnya.

Contoh:

• jumlah data → n
• jumlah karakter → n
• jumlah node → n
• jumlah mahasiswa → n
• jumlah kota → n

---

4. Big O Berbicara Tentang Pertumbuhan

Misalnya terdapat tiga algoritma:

A = 10
B = n
C = n²

Untuk:

n = 10

hasilnya:

A = 10
B = 10
C = 100

Untuk:

n = 100

hasilnya:

A = 10
B = 100
C = 10.000

Untuk:

n = 1.000

hasilnya:

A = 10
B = 1.000
C = 1.000.000

Perhatikan:

A → tetap
B → bertambah secara linear
C → bertambah secara kuadrat

Inilah inti konsep Big O.

---

5. Kompleksitas Konstan — O(1)

O(1) disebut constant time.

Artinya:

Jumlah operasi tidak bergantung pada ukuran input.

Contoh:

Ambil data pertama

Tidak peduli:

n = 10
n = 1.000
n = 1.000.000

Operasinya tetap kira-kira satu langkah.

O(1)

Gambaran

n kecil  → 1 operasi
n besar  → 1 operasi
n sangat besar → 1 operasi

---

6. Kompleksitas Linear — O(n)

O(n) disebut linear time.

Artinya:

Jika jumlah data bertambah 2 kali, jumlah operasi kira-kira bertambah 2 kali.

Contoh:

n = 10
→ 10 operasi

n = 100
→ 100 operasi

n = 1.000
→ 1.000 operasi

Hubungannya:

Jumlah operasi ≈ n

Maka:

O(n)

---

7. Kompleksitas Logaritmik — O(log n)

O(log n) terjadi ketika ukuran masalah dikurangi secara signifikan pada setiap langkah, sering kali menjadi setengah.

Contoh:

n = 16

Jika setiap langkah dibagi dua:

16
↓
8
↓
4
↓
2
↓
1

Hanya membutuhkan sekitar:

4 langkah

Karena:

log₂(16) = 4

Contoh lain:

n = 1.024

1.024
512
256
128
64
32
16
8
4
2
1

Hanya sekitar:

10 langkah

Karena:

log₂(1024) = 10

Itulah mengapa O(log n) sangat efisien untuk input besar.

---

8. Kompleksitas Linearithmic — O(n log n)

O(n log n) merupakan kombinasi:

n × log n

Contohnya banyak ditemukan pada algoritma sorting yang efisien.

Misalnya:

n = 1.000

maka secara kasar:

n log₂ n
≈ 1.000 × 10
≈ 10.000

Sedangkan:

n²
= 1.000.000

Sehingga O(n log n) jauh lebih baik daripada O(n²) untuk data besar.

---

9. Kompleksitas Kuadratik — O(n²)

O(n²) berarti pertumbuhan operasi mengikuti:

n × n

Misalnya:

n	n²
10	100
100	10.000
1.000	1.000.000
10.000	100.000.000

Terlihat bahwa sedikit peningkatan n dapat menyebabkan peningkatan operasi yang sangat besar.

O(n²) sering muncul ketika:

Setiap data dibandingkan dengan setiap data lainnya.

---

10. Kompleksitas Kubik — O(n³)

O(n³):

n × n × n

Contoh:

n	n³
10	1.000
100	1.000.000
1.000	1.000.000.000

Pertumbuhannya jauh lebih cepat daripada O(n²).

---

11. Kompleksitas Eksponensial — O(2ⁿ)

O(2ⁿ) berarti pertumbuhan berdasarkan pangkat 2.

Contoh:

n	2ⁿ
1	2
5	32
10	1.024
20	1.048.576
30	1.073.741.824
40	1.099.511.627.776

Perhatikan betapa cepat pertumbuhannya.

Karena itu algoritma O(2ⁿ) biasanya menjadi tidak praktis untuk n yang besar.

---

12. Kompleksitas Faktorial — O(n!)

Pertumbuhan faktorial bahkan lebih cepat.

n! = n × (n-1) × (n-2) × ... × 1

Contoh:

n	n!
5	120
10	3.628.800
15	1.307.674.368.000
20	2.432.902.008.176.640.000

O(n!) biasanya muncul pada pendekatan brute force terhadap semua kemungkinan/permutasi.

---

13. Urutan Pertumbuhan Big O

Secara umum:

O(1)
   ↓
O(log n)
   ↓
O(n)
   ↓
O(n log n)
   ↓
O(n²)
   ↓
O(n³)
   ↓
O(2ⁿ)
   ↓
O(n!)

Semakin ke bawah:

Pertumbuhan kompleksitas semakin cepat.

Namun perlu dipahami bahwa “lebih baik” bergantung pada konteks dan ukuran input.

---

14. Tabel Perbandingan

Misalkan:

n = 1.000

Perkiraan pertumbuhan:

Kompleksitas	Pertumbuhan
O(1)	1
O(log n)	≈ 10
O(n)	1.000
O(n log n)	≈ 10.000
O(n²)	1.000.000
O(n³)	1.000.000.000
O(2ⁿ)	sangat besar
O(n!)	sangat besar

Ini memberikan gambaran mengapa pemilihan algoritma sangat penting.

---

15. Konsep Growth Rate

Salah satu konsep paling penting dalam Big O adalah:

Growth Rate

Growth rate adalah seberapa cepat jumlah operasi bertambah ketika n bertambah.

Bandingkan:

O(n)

dengan:

O(n²)

Jika n menjadi 2 kali:

O(n)
→ 2 kali lebih banyak

Sedangkan:

O(n²)
→ 4 kali lebih banyak

Jika n menjadi 10 kali:

O(n)
→ 10 kali

O(n²)
→ 100 kali

Inilah alasan utama mengapa O(n²) menjadi bermasalah ketika data sangat besar.

---

16. Mengapa Konstanta Diabaikan?

Misalnya:

T(n) = 5n

Secara Big O:

O(n)

Mengapa?

Karena Big O memperhatikan pola pertumbuhan, bukan konstanta.

Bandingkan:

5n
10n
100n

Semuanya tetap bertumbuh secara linear.

Maka:

5n     → O(n)
10n    → O(n)
100n   → O(n)

---

17. Mengapa Suku yang Lebih Rendah Diabaikan?

Misalnya:

T(n) = n² + n + 10

Untuk n besar:

n²

jauh lebih dominan dibandingkan:

n

dan:

10

Maka:

O(n² + n + 10)

disederhanakan menjadi:

O(n²)

---

18. Aturan Dominasi

Urutan dominasi:

n!
>
2ⁿ
>
n³
>
n²
>
n log n
>
n
>
log n
>
1

Jika terdapat:

n² + n + log n + 100

maka yang dominan adalah:

n²

Jadi:

O(n²)

---

19. Operasi Berurutan

Misalnya sebuah algoritma melakukan:

Proses A = O(n)

Proses B = O(n)

Proses C = O(n²)

Total:

O(n) + O(n) + O(n²)

Secara sederhana:

O(2n + n²)

Ambil pertumbuhan terbesar:

O(n²)

Prinsip

Untuk proses yang dilakukan berurutan, kompleksitas dijumlahkan kemudian disederhanakan berdasarkan suku dominan.

---

20. Operasi Bersarang

Misalnya:

Proses A
    ↓
n operasi

Untuk setiap operasi:
    ↓
n operasi

Maka:

n × n

sehingga:

O(n²)

Jika tiga tingkat:

n × n × n

maka:

O(n³)

Prinsip

Operasi yang bersarang biasanya dikalikan.

---

21. Contoh Analisis Tanpa Python

Perhatikan algoritma:

1. Ambil data pertama
2. Periksa semua data
3. Bandingkan setiap data dengan semua data lainnya

Analisis:

Langkah 1

O(1)

Langkah 2

O(n)

Langkah 3

O(n²)

Total:

O(1) + O(n) + O(n²)

Maka:

O(n²)

---

22. Best Case, Average Case, Worst Case

Big O sering digunakan untuk menggambarkan worst-case upper bound, tetapi analisis algoritma juga mengenal beberapa kondisi.

Best Case

Kondisi terbaik.

Ω(...)

Average Case

Kondisi rata-rata.

Worst Case

Kondisi terburuk.

O(...)

Contoh pencarian linear:

Data:

10 20 30 40 50

Cari:

10

Ditemukan langsung.

Best case:

O(1)

Cari:

50

Harus memeriksa seluruh data.

Worst case:

O(n)

---

23. Big O Bukan Jumlah Operasi Persis

Misalnya kita mengatakan:

O(n)

Bukan berarti:

tepat n operasi

Bisa saja algoritma melakukan:

3n + 5

atau:

10n + 100

Tetapi pertumbuhannya tetap linear.

Maka:

O(n)

Jadi Big O adalah klasifikasi pertumbuhan, bukan perhitungan jumlah operasi secara persis.

---

24. Big O Bukan Waktu Absolut

Misalnya:

Algoritma A → O(n)
Algoritma B → O(n²)

Tidak otomatis berarti A selalu lebih cepat untuk semua ukuran input.

Untuk n yang sangat kecil, faktor konstanta dan implementasi bisa berpengaruh.

Big O terutama berguna untuk menjawab:

Bagaimana performa algoritma ketika input semakin besar?

---

25. Konsep Asymptotic Analysis

Big O termasuk dalam analisis asimtotik.

Artinya kita tertarik pada perilaku algoritma ketika:

n → sangat besar

Contoh:

T(n) = n² + 100n + 500

Ketika n sangat besar:

n²

menjadi faktor yang paling dominan.

Maka:

T(n) = O(n²)

---

26. Contoh Berpikir Big O

Jangan langsung menghafal:

for → O(n)
nested for → O(n²)

Yang lebih penting adalah memahami pertanyaannya:

Pertanyaan 1

Berapa kali proses dijalankan?

Pertanyaan 2

Apakah jumlah proses bergantung pada n?

Pertanyaan 3

Apakah ada proses yang berulang?

Pertanyaan 4

Apakah proses dilakukan bersarang?

Pertanyaan 5

Apakah ukuran masalah berkurang setiap langkah?

Pertanyaan 6

Mana pertumbuhan yang paling dominan?

---

27. Case Study Konsep

Kasus: Perpustakaan

Sebuah perpustakaan memiliki:

10 buku

Kemudian berkembang menjadi:

100 buku

Kemudian:

1.000 buku

Kemudian:

100.000 buku

Ada tiga metode pencarian.

Metode A

Selalu langsung menuju lokasi data.

O(1)

Metode B

Memeriksa buku satu per satu.

O(n)

Metode C

Setiap langkah membuang setengah kemungkinan.

O(log n)

Pertanyaannya:

Ketika jumlah buku menjadi 100.000, metode mana yang paling skalabel?

Jawaban:

O(1)

dan

O(log n)

jauh lebih baik dalam pertumbuhan dibanding:

O(n)

---

28. Case Study Perbandingan

Misalnya terdapat:

n = 10
n = 100
n = 1.000
n = 10.000

Hitung:

O(1)
O(log₂ n)
O(n)
O(n log₂ n)
O(n²)

Tabel

n	O(1)	O(log n)	O(n)	O(n log n)	O(n²)
10	1	≈3	10	≈33	100
100	1	≈7	100	≈664	10.000
1.000	1	≈10	1.000	≈9.966	1.000.000
10.000	1	≈13	10.000	≈132.877	100.000.000

Dari tabel tersebut terlihat jelas:

O(1)
O(log n)

tumbuh sangat lambat.

Sedangkan:

O(n²)

tumbuh sangat cepat.

---

29. Kesalahan Umum Saat Belajar Big O

Kesalahan 1

Menganggap:

O(n) = n detik

❌ Salah.

Big O bukan satuan waktu.

---

Kesalahan 2

Menganggap:

O(2n) berbeda dengan O(n)

Untuk klasifikasi Big O:

O(2n) = O(n)

---

Kesalahan 3

Menganggap:

O(n + n²) = O(n³)

❌ Salah.

Yang dominan:

n²

Jadi:

O(n²)

---

Kesalahan 4

Menganggap semua for pasti O(n).

Tidak selalu.

Contoh:

for
    for

bisa menjadi:

O(n²)

---

Kesalahan 5

Menganggap Big O adalah benchmark komputer.

❌ Bukan.

Benchmark:

0.002 detik

Big O:

O(n)

---

30. Latihan Konsep

Soal 1

Tentukan Big O:

T(n) = 10

Jawaban:

O(1)

---

Soal 2

T(n) = 5n

Jawaban:

O(n)

---

Soal 3

T(n) = 3n² + 5n + 10

Jawaban:

O(n²)

---

Soal 4

T(n) = n³ + n² + n

Jawaban:

O(n³)

---

Soal 5

T(n) = n log n + n

Jawaban:

O(n log n)

---

Soal 6

T(n) = 2ⁿ + n²

Jawaban:

O(2ⁿ)

---

31. Latihan Analisis

Tentukan Big O dari:

A

T(n) = 100

B

T(n) = 20n + 50

C

T(n) = n² + 100n

D

T(n) = 5n³ + 2n² + n

E

T(n) = n log n + 100n

F

T(n) = 2ⁿ + n³ + n

Kunci

A → O(1)

B → O(n)

C → O(n²)

D → O(n³)

E → O(n log n)

F → O(2ⁿ)

---

32. Rangkuman Konsep Big O

Mahasiswa minimal harus memahami 8 konsep utama berikut:

1. n = ukuran input

2. Big O = pertumbuhan kompleksitas

3. O(1) = konstan

4. O(log n) = logaritmik

5. O(n) = linear

6. O(n log n) = linearithmic

7. O(n²) = kuadratik

8. O(2ⁿ) = eksponensial

Kemudian pahami aturan:

Konstanta diabaikan
        ↓
Suku dominan yang dipakai
        ↓
Operasi berurutan → dijumlahkan
        ↓
Operasi bersarang → dikalikan
        ↓
Input dibagi → sering O(log n)

Big O bukan tentang seberapa cepat program berjalan sekarang, tetapi tentang bagaimana pertumbuhan kebutuhan operasi ketika ukuran input n semakin besar.

Kalau konsep ini sudah benar-benar dipahami, barulah masuk ke analisis kode Python. Dengan begitu mahasiswa tidak sekadar menghafal “for = O(n)“, tetapi mampu menurunkan Big O dari logika algoritmanya.