Big-O nerangake carane runtime utawa memori saka algoritma tuwuh nalika ukuran input n tuwuh. Iku nangkep tingkah laku asimtotik ing kasus paling elek, ngabaikan konstanta lan suku tingkat ngisor.
Kita peduli marang tingkat tuwuh, dudu jumlah langkah sing persis. O(2n + 5) tinimbang O(n) amerga nalika n gedhe, konstanta lan suku sing luwih cilik ora penting.
| Big-O | Jeneng | Conto |
|---|
| O(1) | konstan | panggilan indeks array |
| O(log n) | logaritmik | pencarian biner |
| O(n) | linear | pindai daftar |
| O(n log n) | linearitmik | 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 nyembunyake konstanta: algoritma O(n) kanthi konstanta gedhe bisa ilang marang O(n log n) ing input cilik. Uga lacak kompleksitas spasi, ora mung wektu.
Big-O ngidini sampeyan mbandingi algoritma tanpa running mbandingi atau kuatir bakal hardware.
Iku predictkan solusi endi sing isih urip nalika input tuwuh saka atusan nganti jutaan — beda antarane fitur sing skalabel lan siji sing timeout.
Iku kosakata sing saben insinyur nggunakake nggo reasoning bakal performance.