Što je Big-O notacija?

Question

Accepted Answer

**Big-O** opisuje kako se vrijeme izvršavanja ili memorija algoritma povećavaju kako raste veličina ulaza **n**. Hvaća *najgori slučaj* asimptotskog ponašanja, ignorirajući konstante i članove nižeg reda.

## Osnovna ideja

Brinemo se o brzini rasta, ne o točnom broju koraka. O(2n + 5) je jednostavno **O(n)** jer kako n raste, konstante i manji članovi prestaju biti važni.

## Česte klase

| Big-O | Naziv | Primjer |
|-------|-------|----------|
| O(1) | konstantna | pristup elementu niza |
| O(log n) | logaritamska | binarno pretraživanje |
| O(n) | linearna | skeniranje liste |
| O(n log n) | linearitmička | merge sort |
| O(n²) | kvadratna | ugniježđene petlje |
| O(2ⁿ) | eksponencijalna | naivni podskupovi |

## Primjer

```python
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
```

## Česte greške

Big-O skriva konstante: algoritam s O(n) i ogromnom konstantom može izgubiti od O(n log n) na malim ulazima. Također pratite **prostornu** složenost, ne samo vremensku.

## Zašto je važno

Big-O vam omogućava usporedbu algoritama bez pokretanja ili brige o hardveru.

Predviđa koja rješenja prežive kada ulazi rastu od stotina na milijune — razlika između funkcionalnosti koja se skalira i one koja istekne.

To je vokabular koji svaki inženjer koristi da razmisli o performansama.

O(1)	konstantna	pristup elementu niza
O(log n)	logaritamska	binarno pretraživanje
O(n)	linearna	skeniranje liste
O(n log n)	linearitmička	merge sort
O(n²)	kvadratna	ugniježđene petlje
O(2ⁿ)	eksponencijalna	naivni podskupovi