Big-O menjelaskan bagaimana waktu berjalan atau memori dari algoritma tumbuh seiring dengan bertambahnya ukuran input n. Ia menangkap perilaku asimptotik kasus terburuk, mengabaikan konstanta dan suku orde lebih rendah.
Kami peduli dengan laju pertumbuhan, bukan jumlah langkah yang tepat. O(2n + 5) hanyalah O(n) karena seiring n membesar, konstanta dan suku yang lebih kecil menjadi tidak 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) | linear-logaritmik | merge sort |
| O(n²) | kuadrat | loop bersarang |
| 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.
Itu memprediksi solusi mana yang bertahan ketika input tumbuh dari ratusan ke jutaan — perbedaan antara fitur yang dapat diskalakan dan yang kehabisan waktu.
Ini adalah kosakata yang digunakan setiap insinyur untuk bernalar tentang kinerja.