# Measuring Algorithms Without a Stopwatch — Time & Space Complexity (Big-O)

Source: https://www.skillbyai.com/en/big-o/f-why

> Explain why we count steps as a function of input size instead of timing programs.

## Growth, not seconds

Timing a program tells you how fast it ran on one machine, with one input, in one language, on one day. Change any of those and the number changes. **Algorithm analysis** asks a more durable question: **how does the amount of work grow as the input grows?** We describe input size with **n** (the number of elements in an array, characters in a string, vertices in a graph) and count the **basic operations** an algorithm performs (comparisons, assignments, arithmetic) as a function of n. If doubling the input doubles the work, the algorithm scales **linearly**; if doubling the input quadruples the work, it scales **quadratically**, and for large inputs that difference dwarfs any difference in hardware. Complexity analysis lets you compare algorithms on paper, predict whether a solution will finish in time for a given input size, and explain design choices in interviews and code reviews. It complements, but does not replace, **measuring** real performance.

## Growth curves diverge

For small inputs most algorithms look similar; as n grows, the curves separate dramatically.

![Several curves starting near the origin: a flat line, a gentle curve, a straight diagonal, and two curves bending sharply upward.](assets/figures/big-o/section-1-map.svg) — Figure 1.1 — Different growth rates as input size increases.

## Two ways to check for duplicates

Both are correct; their growth is very different.

```python
def has_duplicate_pairs(items):
    # compare every pair: about n*n/2 comparisons
    n = len(items)
    for i in range(n):
        for j in range(i + 1, n):
            if items[i] == items[j]:
                return True
    return False

def has_duplicate_set(items):
    # one pass with a set: about n hash operations
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

# for 100,000 items: roughly 5,000,000,000 comparisons vs roughly 100,000 set operations
```

## Hardware does not fix bad growth

A computer ten times faster lets a quadratic algorithm handle only about three times larger inputs in the same time. Improving the growth rate usually beats buying faster machines.

**Quiz:** What does complexity analysis primarily describe?

- [x] How the work grows as the input size grows
- [ ] The exact running time in seconds
- [ ] The number of lines of code
- [ ] The programming language used

*Answer:* How the work grows as the input size grows. Complexity describes growth as a function of n, independent of machine details.