Big O Notation Explained with Examples

Big O notation describes how an algorithm's running time or memory use grows as the input gets larger. It ignores constant factors and small inputs, and focuses on the growth rate that dominates for large n.

This guide explains Big O notation with examples: the formal definition, the common complexity classes, rules for analysing loops and recursion, related notations, and worked code examples in Python. It ends with common mistakes and how STEM Donkey can help with complexity analysis.

What Big O Notation Means

Formally, f(n) = O(g(n)) if there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ c·g(n) for every n ≥ n₀. In words, beyond some input size, f is never more than a constant multiple of g.

The "=" in f(n) = O(g(n)) is a convention, not true equality. It reads as "f is in the set of functions that grow no faster than g". That is why 3n is O(n) and also, technically, O(n²): an upper bound does not have to be tight.

Common Complexity Classes

The table lists the classes you will meet most often, from fastest to slowest growth. The last column shows roughly how many basic steps each implies when n = 1,000.

The numbers show why growth rate matters more than speed of hardware. A faster computer helps an O(n log n) algorithm on large inputs; it cannot rescue an O(2ⁿ) one.

Rules for Simplifying Big O

• Drop constant factors: 5n is O(n), and n/2 is O(n).
• Keep only the dominant term: n² + 100n + 7 is O(n²).
• Sequential steps add: an O(n) step followed by an O(n²) step is O(n + n²) = O(n²).
• Nested steps multiply: an O(n) loop inside an O(n) loop is O(n²).
• Different inputs keep different letters: looping over a list of size n and then a list of size m is O(n + m), not O(n).
• Log bases do not matter: log₂ n and log₁₀ n differ by a constant factor, so both are O(log n).

Analysing Loops, with Code

For iterative code, count how many times the innermost operation runs in the worst case.

def has_duplicate_pairs(items):
    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):
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

Watch for loops whose counter does not step by one. A loop where i doubles each time (i = 1, 2, 4, 8, ...) runs about log₂ n times, so it is O(log n).

Analysing Recursive Algorithms

For recursive code, write a recurrence relation for the running time T(n), then solve it.

The master theorem solves recurrences of the form T(n) = aT(n/b) + f(n), where a ≥ 1 and b > 1. It compares f(n) with n^(log_b a). For merge sort, a = 2 and b = 2, so n^(log₂ 2) = n, which matches f(n) = n and gives O(n log n).

A recursion tree is a good check. For merge sort, each level does O(n) work in total and there are about log₂ n levels, which gives the same answer.

Big O, Big Omega and Big Theta

In everyday use, people often say "Big O" when they mean a tight bound. In an algorithms assignment, use Θ when you have shown both bounds, and say which case you mean.

Best, Average and Worst Case

One algorithm can have different bounds depending on the input. Always say which case you are analysing.

• Insertion sort: best case O(n) on already sorted input, worst case O(n²) on reverse-sorted input.
• Quicksort: average O(n log n), worst case O(n²) with consistently poor pivots.
• Hash table lookup: average O(1), worst case O(n) when many keys collide.
• Amortised cost: appending to a Python list is O(1) amortised. An occasional resize costs O(n), but spread across many appends the average per append stays constant.

Space Complexity

Big O also describes memory. Count the extra memory an algorithm uses beyond its input.

• Swapping elements in place uses O(1) extra space.
• Building a set of seen items uses O(n) extra space.
• Recursion uses stack space: a recursion depth of n means O(n) space even if each call stores little.
• Merge sort on arrays typically needs O(n) extra space for merging.

Time and space often trade against each other, as in the duplicate check above. A good answer names the trade-off.

Common Big O Mistakes

Complexity analysis rewards patience. Count step by step, one loop at a time, and the answer usually falls out without guesswork.

How STEM Donkey Helps with Big O and Complexity Analysis

Send your algorithms questions, code or pseudocode and your course notes. A writer matched to your level prepares a custom solution that counts operations, writes and solves recurrences, states the case analysed and justifies each bound, with clear explanations.

Use it to understand the method, then analyse similar algorithms yourself. Free revisions within the original scope are included for 14 days.