Big-O time complexity

Why count steps, not seconds

The same program takes different times on a new laptop and an old phone, so seconds are a poor way to compare ideas. Instead we count basic steps: one comparison, one addition, one read from a list. We call the input size n (for example, the number of items in a list). Time complexity is how the number of steps grows as n grows.

Big-O notation writes that growth in a short form. O(n), read "order n", means the steps grow in proportion to n: double the input and you roughly double the work. Big-O usually describes the worst case, the input that makes your code work hardest.

Drop constants and smaller terms

If your code takes 3n + 5 steps, we write O(n). If it takes n² + 100n steps, we write O(n²). The reason is that for large n the biggest term wins: with n = 1,000,000, n² is a million million while 100n is only a hundred million. Constants like 3 depend on the machine and language; the shape of the growth does not.

def first_item(nums):          # O(1): one step, whatever n is
    return nums[0]

def total(nums):               # O(n): one step per item
    s = 0
    for x in nums:
        s += x
    return s

def all_pairs(nums):           # O(n²): n steps for each of n items
    pairs = []
    for a in nums:
        for b in nums:
            pairs.append((a, b))
    return pairs

print(total([1, 2, 3]))        # Output: 6
print(len(all_pairs([1, 2, 3])))  # Output: 9

The common classes

A rough rule of thumb: a computer does about 10⁸ simple operations per second in a fast compiled language like C++, and Python is often 10 to 50 times slower. So with n = 10⁶, an O(n log n) idea finishes in well under a second, while an O(n²) idea needs about 10¹² steps, which is hours. Treat these numbers as rough guides, not exact timings.

Sequential versus nested loops

Two loops one after another ADD: O(n) + O(n) = O(2n), which is still O(n). A loop inside a loop MULTIPLIES: n steps of the outer loop, each doing n steps, is O(n²). If the two loops run over different inputs of sizes n and m, the costs are O(n + m) and O(n × m); do not merge them into one letter.

def has_duplicate_slow(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

def has_duplicate_fast(nums):
    seen = set()
    for x in nums:
        if x in seen:          # a set lookup is O(1) on average
            return True
        seen.add(x)
    return False

print(has_duplicate_slow([3, 1, 3]), has_duplicate_fast([3, 1, 3]))  # Output: True True

Common mistakes

• Missing hidden loops. x in a_list, a_list.index(x) and a_list.count(x) each scan the whole list, so using them inside a loop gives O(n²). Fix: use a set or dict for lookups.
• Keeping constants: writing O(2n) or O(n/2). Fix: both are O(n).
• Merging different inputs: a loop over n users inside a loop over m products is O(n × m), not O(n²). Fix: give each input its own letter.
• Thinking every "two loops" is O(n²). Fix: check whether the loops are nested or one after the other, and how far each one runs.
• Worrying about the base of a logarithm. Fix: log₂ n and log₁₀ n differ only by a constant, so both are just O(log n).