# Mengapa bubble-sort memiliki kompleksitas algoritma O(n2)?

Bubble Sort adalah algoritma pengurutan yang bekerja dengan cara membandingkan dua elemen yang berdekatan (berurutan dalam array)
dan menukarnya jika urutannya salah. Proses ini bisa dilakukan berulang kali (dalam beberapa “pass”) sampai seluruh data dalam array sudah pada posisi yang benar atau urut.


Bayangkan jika kita memiliki (n) buah buku yang perlu diurutkan berdasarkan tinggi. Dengan bubble sort, kita akan:

- Pass pertama: Bandingkan dan tukar buku 1-2, 2-3, 3-4, ..., (n-1)-n
-> (n-1) kali pembandingan
- Pass kedua: Bandingkan dan tukar buku 1-2, 2-3, ..., (n-2)-(n-1)
-> (n-2) kali pembandingan
- Dan seterusnya, hingga pass terakhir hanya melakukan 1 kali perbandingan.

- Pass terakhir: 1 kali pembandingan

Total operasi
= (n-1) + (n-2) + (n-3) + ... + 1
= n(n-1)/2

Meskipun hasilnya adalah n(n-1)/2, ketika dihitung dalam notasi Big-O,
kita hanya melihat komponen yang paling dominan, yaitu n². Karena itu kompleksitasnya adalah O(n²)

Intinya, kenapa Bubble sort memiliki kompleksitas O(n²), karena:
- Nested loops yang masing-masing bergantung linear pada n
- Jumlah operasi tumbuh secara kuadratik terhadap ukuran data
- n(n-1)/2 yang dalam notasi BigO disederhanakan menjadi O(n²)

Pros and cons menggunakan algoritma bubbleSort:
Pros:
- cocok untuk dataset yang kecil (misalnya <1000 elemen)
- mudah diimplementasi dan di pahami
Cons:
- tidak efesien untuk dataset besar
- bertambahnya kuadratik membuatnya tidak scalable