# Big-O & Complexity — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/big-o

> Big-O describes how running time or memory grows as input grows.

## Growth, not stopwatch

Big-O ignores constants and machine speed and asks: **if input doubles, what happens to the work?** `O(1)` unchanged, `O(log n)` grows by one step, `O(n)` doubles, `O(n log n)` slightly more than doubles, `O(n^2)` quadruples.

## Reading complexity from loops

A single pass over `n` items is `O(n)`. A loop inside a loop over the same data is `O(n^2)`. Halving the range each step is `O(log n)`.

```python
for x in arr:            # O(n)
    print(x)

for i in arr:            # O(n^2)
    for j in arr:
        print(i, j)

lo, hi = 0, len(arr) - 1 # O(log n)
while lo <= hi:
    mid = (lo + hi) // 2
    ...
```

## Time vs space

Space complexity counts *extra* memory beyond the input — a few variables is `O(1)`, a copy of the array is `O(n)`, a recursion depth of `n` is `O(n)` stack space. Interviewers often ask you to trade one for the other.

**Quiz:** Input goes from 1,000 to 1,000,000. An O(log n) step count roughly...

- [ ] Triples
- [x] Grows by ~10 steps
- [ ] Grows 1000x

*Answer:* Grows by ~10 steps. log2(1e6) - log2(1e3) is about 20 - 10 = 10 extra steps.