# Pitfalls and Real-World Performance — Time & Space Complexity (Big-O)

Source: https://www.skillbyai.com/en/big-o/p-pitfalls

> Avoid common analysis mistakes and remember what Big-O does not capture.

## What Big-O leaves out

Common analysis mistakes: forgetting the cost of **library calls** (`in` on lists, slicing, string concatenation); ignoring **recursion stack space**; confusing **best case** with typical behaviour; writing O(n²) when two **different inputs** call for O(n · m); claiming a nested loop is quadratic when amortised reasoning shows it is linear; and forgetting the **log factor** of sorting. Big-O also hides things that matter in practice. **Constant factors**: an O(n) algorithm that does 50 operations per element can lose to an O(n log n) one doing 2 per element for realistic n. **Memory hierarchy**: contiguous arrays are often much faster than linked structures with the same complexity, because of CPU caches. **Small inputs**: for n below a few dozen, simple O(n²) algorithms can beat sophisticated ones, which is why libraries switch to insertion sort for small slices. **I/O and network**: one database round trip can cost more than millions of CPU operations. Use complexity to choose sensible approaches, then **measure** with profilers and benchmarks to confirm.

## Same complexity, different speed

Both functions are O(n), but memory layout and constants differ.

```python
import array

# summing 10 million numbers: both O(n)
nums_list = list(range(10_000_000))
nums_packed = array.array("q", range(10_000_000))

total_a = sum(nums_list)          # list of pointers to integer objects
total_b = sum(nums_packed)        # compact array of machine integers

# with NumPy, a vectorised sum runs in optimised C over contiguous memory:
# import numpy as np; total_c = np.arange(10_000_000).sum()
# expect large constant-factor differences even though all are O(n);
# measure with timeit on your machine rather than assuming
```

## Optimise the right thing

Profile before optimising. A function with excellent complexity can still be the bottleneck because it makes a network call per item; reducing round trips often matters more than shaving a log factor.

**Quiz:** Why might an O(n log n) algorithm beat an O(n) algorithm in practice for realistic input sizes?

- [x] Constant factors, memory access patterns and implementation details can outweigh the asymptotic difference
- [ ] Big-O is always wrong
- [ ] O(n log n) is always faster
- [ ] log n is negative for large n

*Answer:* Constant factors, memory access patterns and implementation details can outweigh the asymptotic difference. Asymptotic notation hides constants and hardware effects that dominate for moderate n.