Rules for Simplifying Complexity

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.

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.

त्वरित जाँच: 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?

• O(n log m)
• O(n + m)
• O(n²)
• O(log n)