# Why Data Structures and Big-O Matter — Data Structures in Python

Source: https://www.skillbyai.com/en/data-structures-python/f-bigo

> Reason about time and space complexity of operations.

## Choosing structures by their costs

A **data structure** organises data so that certain operations are efficient. The same task can take milliseconds or hours depending on the structure: checking whether an item is in a `list` of a million elements scans it (**O(n)**), while a `set` answers in **O(1)** on average. **Big-O notation** describes how running time or memory grows with input size `n`, ignoring constant factors: **O(1)** constant, **O(log n)** logarithmic (binary search, balanced trees, heaps), **O(n)** linear (one pass), **O(n log n)** (good sorting), **O(n²)** quadratic (nested loops over the data) and **O(2ⁿ)** exponential. Distinguish **worst case**, **average case** and **amortised** cost (the average over a sequence of operations, as with `list.append`, which occasionally resizes but is O(1) amortised). **Space complexity** matters too: an index can trade memory for speed. In Python, constant factors are larger than in C because every value is an object, so measure as well as reason, and remember that the built-in structures (`list`, `dict`, `set`, `deque`, `heapq`) are implemented in C and are usually faster than hand-written Python equivalents.

## Growth rates

How running time grows with input size for common complexity classes.

![A line chart with input size on the horizontal axis and time on the vertical axis, showing a flat line, a slowly rising curve, a straight diagonal, a steeper curve and a nearly vertical curve.](assets/figures/data-structures-python/section-1-map.svg) — Figure 1.1 — O(1), O(log n), O(n), O(n log n) and O(n²).

## Membership: list versus set

The same question with O(n) and O(1) average costs.

```python
import time

n = 1_000_000
ids_list = list(range(n))
ids_set = set(ids_list)
queries = [n - 1, n // 2, -5] * 100            # 300 lookups, mostly near the end

start = time.perf_counter()
hits_list = sum(1 for q in queries if q in ids_list)   # each 'in' scans: O(n)
list_time = time.perf_counter() - start

start = time.perf_counter()
hits_set = sum(1 for q in queries if q in ids_set)     # each 'in' hashes: O(1) average
set_time = time.perf_counter() - start

print(hits_list == hits_set)                   # True: same answer
print(f"list: {list_time:.3f}s  set: {set_time:.6f}s")
# The set is typically thousands of times faster here; exact numbers depend on the machine.
```

## Count the passes

A quick way to estimate complexity: one loop over the data is O(n); a loop containing a scan of the same data (like `x in some_list`) is O(n²). Replacing the inner scan with a set or dict lookup often turns minutes into milliseconds.

**Quiz:** What does amortised O(1) mean for list.append?

- [x] Occasional resizes are expensive, but the average cost over many appends is constant
- [ ] Every append takes exactly the same time
- [ ] Append is O(n) always
- [ ] Append never allocates memory

*Answer:* Occasional resizes are expensive, but the average cost over many appends is constant. Over-allocation spreads the cost of occasional copies across many cheap appends.