# Counting Operations and Best, Worst and Average Cases — Time & Space Complexity (Big-O)

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

> Count operations for simple code and distinguish best, worst and average cases.

## One algorithm, several behaviours

To analyse an algorithm, count how many times its basic operations run as a function of n. Statements that run once cost a constant; a loop that runs n times multiplies its body's cost by n. Often the count depends on the **particular input**, not just its size, so we distinguish cases. The **worst case** is the maximum work over all inputs of size n: for **linear search**, the target is last or absent, so n comparisons. The **best case** is the minimum: the target is first, so 1 comparison. The **average case** is the expected work under some assumption about inputs: if the target is equally likely to be anywhere, about n/2 comparisons. Worst-case analysis is the most common because it gives a **guarantee** and does not depend on assumptions about input distributions. Average-case analysis matters for algorithms like **quicksort** and **hash tables**, whose typical behaviour is much better than their worst case.

## Linear search with its operation counts

The number of comparisons depends on where (or whether) the target appears.

```python
def linear_search(items, target):
    for i, x in enumerate(items):   # runs up to n times
        if x == target:             # 1 comparison per iteration
            return i
    return -1

# best case:    target at index 0        -> 1 comparison
# worst case:   target absent or last    -> n comparisons
# average case: target equally likely at any index -> about n / 2 comparisons
# all three grow linearly with n except the best case, which is constant
```

## Looking for your keys

Searching pockets one by one: best case they are in the first pocket, worst case in the last (or not on you at all), and on an average day somewhere in the middle. You plan your morning around the worst case if you cannot be late.

**Quiz:** For linear search on an array of n elements, what is the worst-case number of comparisons?

- [ ] 1
- [ ] log n
- [ ] n²
- [x] n

*Answer:* n. In the worst case every element is compared once, giving n comparisons.