# Rules for Simplifying Complexity — Time & Space Complexity (Big-O)

Source: https://www.skillbyai.com/en/big-o/n-rules

> Apply the sum, product, logarithm and multiple-variable rules.

## Shortcuts that follow from the definition

A few rules let you simplify quickly. **Drop constants**: O(5n) = O(n). **Drop lower-order terms**: O(n² + n) = O(n²). **Sum rule**: sequential steps add, and the larger term wins, so an O(n) loop followed by an O(n²) loop is O(n²). **Product rule**: nested work multiplies, so an O(n) loop whose body is O(log n) is O(n log n). **Logarithm bases do not matter**: log₂ n and log₁₀ n differ only by a constant factor, so we just write O(log n). But **exponents do matter**: 2ⁿ and 3ⁿ are different classes, and so are n² and n³. **Multiple inputs keep separate variables**: iterating over an array of size n and then over a list of size m is O(n + m); comparing every element of one with every element of the other is O(n · m). Do not simplify O(n · m) to O(n²) unless you know m is proportional to n. Finally, complexity depends on what you define as n: for a number N, an algorithm that loops N times is linear in the **value** but exponential in the **number of digits**.

## Applying the rules to a function

Sequential parts add; nested parts multiply.

```python
def report(orders, customers):
    total = sum(o.amount for o in orders)          # O(n), n = len(orders)

    orders.sort(key=lambda o: o.date)              # O(n log n)

    by_id = {c.id: c for c in customers}           # O(m), m = len(customers)
    for o in orders:                               # O(n) iterations ...
        o.customer = by_id[o.customer_id]          # ... of O(1) average work

    return total

# total: O(n) + O(n log n) + O(m) + O(n) = O(n log n + m)
```

## Keep both variables

Interviewers like to see O(n + m) or O(n · m) instead of a premature O(n²). It shows you noticed there are two independent inputs, for example rows and columns of a grid, or a text and a pattern.

**Quiz:** A function loops over a list of n items and, inside the loop, does a binary search on a sorted array of size m. What is its complexity?

- [x] O(n log m)
- [ ] O(n + m)
- [ ] O(n²)
- [ ] O(log n)

*Answer:* O(n log m). n iterations each costing O(log m) multiply to O(n log m).