Big-O menjelaskan bagaimana waktu berjalan atau memori algoritma tumbuh seiring dengan pertumbuhan ukuran input n. Ini menangkap perilaku asimtotik worst-case, mengabaikan konstanta dan suku orde rendah.
Kita peduli tentang laju pertumbuhan, bukan jumlah langkah yang tepat. O(2n + 5) adalah O(n) karena saat n tumbuh besar, konstanta dan suku yang lebih kecil tidak lagi penting.
| Big-O | Nama | Contoh |
|---|
| O(1) | konstan | pencarian indeks array |
| O(log n) | logaritmik | pencarian biner |
| O(n) | linear | pemindaian daftar |
| O(n log n) | linearitmik | merge sort |
| O(n²) | kuadratik | nested loops |
| O(2ⁿ) | eksponensial | subset naif |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Big-O menyembunyikan konstanta: algoritma O(n) dengan konstanta besar dapat kalah dari O(n log n) pada input kecil. Juga lacak kompleksitas ruang, bukan hanya waktu.
Big-O memungkinkan Anda membandingkan algoritma tanpa menjalankannya atau khawatir tentang perangkat keras.
Ia memprediksi solusi mana yang bertahan ketika input tumbuh dari ratusan menjadi jutaan — perbedaan antara fitur yang dapat diskalakan dan fitur yang kehabisan waktu.
Ini adalah kosakata yang digunakan setiap engineer untuk bernalar tentang performa.