Big O Notation and Time Complexity: A Practical Guide

Big O notation describes how the running time or memory use of an algorithm grows as the input grows. It does not answer "how many seconds does this code take?" but "if the input doubles, how much more work is there?". In algorithm midterms and finals it appears in two forms: "find the complexity of this code" and "compare these two algorithms". This guide gives the intuition first, then the precise definition, then loop and recursion analysis, and finally exercises with solutions.

The examples are in C#; if the syntax is new to you, the post on C# classes and objects is enough of a start, but the loops here look the same in almost any language.

Intuition: We Measure Growth, Not Seconds

The same code runs at different speeds on different computers, so counting seconds measures the machine rather than the algorithm. Instead we write the number of basic operations as a function of the input size n. Suppose some code performs 3n² + 5n + 2 operations. For n = 1000 the 3n² term is 3,000,000 and the 5n term is 5,000: for large n the n² term decides everything. The constant factor 3 also changes with the machine and the compiler. We drop both and say "this algorithm is O(n²)".

The Precise Definition, and O vs Ω vs Θ

f(n) = O(g(n)) means there are constants c > 0 and n₀ such that f(n) ≤ c·g(n) for every n ≥ n₀. In the example above c = 4 and n₀ = 6 work: for n ≥ 6 we have 5n + 2 ≤ n², hence 3n² + 5n + 2 ≤ 4n².

• O (big O) is an upper bound: "grows at most this fast".
• Ω (omega) is a lower bound: "grows at least this fast".
• Θ (theta) is both at once: "grows exactly this fast".

An important detail: 3n² + 5n + 2 is also O(n³); that is true but loose. In an exam you are expected to give the tight bound, which is really Θ; everyday speech calls that "Big O" as well. These three symbols are independent of best case and worst case; I come back to that confusion in the mistakes section.

Common Complexity Classes

From slow-growing to fast-growing: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).

// O(1): independent of the input size
static int First(int[] a) => a[0];

// O(log n): the range halves at every step (array must be sorted)
static int BinarySearch(int[] a, int target)
{
    int low = 0, high = a.Length - 1;
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

// O(n): every element is visited once
static long Sum(int[] a)
{
    long total = 0;
    foreach (int x in a) total += x;
    return total;
}

// O(n²): every pair is checked
static int CountEqualPairs(int[] a)
{
    int count = 0;
    for (int i = 0; i < a.Length; i++)
        for (int j = i + 1; j < a.Length; j++)
            if (a[i] == a[j]) count++;
    return count;
}

// O(2ⁿ): every call spawns two more calls
static long Fib(int n) => n < 2 ? n : Fib(n - 1) + Fib(n - 2);

The typical O(n log n) example is merge sort; its trace and the comparison with the other sorting algorithms are in sorting algorithms exam questions.

How to Analyse Loops

Four rules cover most of the work:

1. Consecutive blocks add up: O(n) + O(n²) = O(n²).
2. Nested loops multiply, but only if the inner loop's iteration count does not depend on the outer one: n × m iterations.
3. If the counter is multiplied or divided (i *= 2, i /= 2), the loop runs log₂ n times.
4. If the inner loop depends on the outer counter (j < i), you sum instead of multiplying: 0 + 1 + ... + (n−1) = n(n−1)/2, which is O(n²).

Rule four is where most mistakes happen. A dependent loop sometimes comes out smaller than n²: see exercises 3 and 7.

Recursion: Linear, Binary and Divide-and-Conquer

For recursive code we ask two things: how many calls are made, and how much work does each call do on its own?

// Linear recursion: n calls, O(1) each -> O(n)
static long SumTo(int n) => n == 0 ? 0 : n + SumTo(n - 1);

// Divide and conquer: two half-size problems + O(n) merge
static void MergeSort(int[] a, int left, int right)
{
    if (left >= right) return;
    int mid = (left + right) / 2;
    MergeSort(a, left, mid);       // T(n/2)
    MergeSort(a, mid + 1, right);  // T(n/2)
    Merge(a, left, mid, right);    // O(n)
}

For SumTo we get T(n) = T(n−1) + O(1): the chain is n links long, so O(n). The Fib above is binary recursion: T(n) = T(n−1) + T(n−2) + O(1). The call tree at most doubles on each level and has depth n, so the upper bound O(2ⁿ) holds (the tight bound is about 1.618ⁿ; exams usually accept O(2ⁿ)).

For merge sort T(n) = 2T(n/2) + O(n). Without heavy maths, think of it like this: on the top level the merge does n work. One level down there are two parts of size n/2, again n in total. Every level costs n in total, and there are log₂ n levels before the parts shrink to one element. Result: n × log n = O(n log n). The Merge method itself is in the sorting post.

The tool that solves such recurrences mechanically is the Master theorem: for T(n) = a·T(n/b) + f(n), compare f(n) with n^(log_b a). Merge sort has a = 2, b = 2, so n^(log₂ 2) = n; f(n) = Θ(n) is of the same order, so case two applies and T(n) = Θ(n log n). Recursive binary search has a = 1, b = 2, f(n) = Θ(1): n^(log₂ 1) = 1, case two again, T(n) = Θ(log n).

Space Complexity

The same notation is used for extra memory; the input itself usually does not count. The part people miss is recursion: every active call occupies stack space. SumTo(n) looks as if it uses a single variable, but its n nested calls cost O(n) memory, and for large n it crashes with a StackOverflowException. Write the same sum as a loop and the space drops to O(1). Merge sort uses an O(n) auxiliary array; Fib(n) runs in exponential time, but at most n calls are active at once, so its space is O(n).

Exercises: What Is the Complexity of This Code?

Solve them yourself first, then check.

// 1
for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        count++;

// 2
for (int i = 1; i < n; i *= 2)
    for (int j = 0; j < n; j++)
        count++;

// 3
for (int i = n; i > 0; i /= 2)
    for (int j = 0; j < i; j++)
        count++;

// 4
for (int i = 0; i < n; i++) count++;
for (int j = 0; j < m; j++) count++;
for (int k = 0; k < n; k++)
    for (int t = 0; t < 100; t++)
        count++;

// 5
int s = 0;
while (s * s < n) s++;

// 6
static int F(int n)
{
    if (n <= 0) return 1;
    return F(n - 1) + F(n - 1);
}

// 7
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j += i)
        count++;

// 8
static int Search(int[] a, int target, int low, int high)
{
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (a[mid] == target) return mid;
    return a[mid] < target
        ? Search(a, target, mid + 1, high)
        : Search(a, target, low, mid - 1);
}

Solutions:

1. The inner loop runs i times: 0 + 1 + ... + (n−1) = n(n−1)/2. O(n²). For n = 16 that is exactly 120 iterations.
2. The outer loop runs log₂ n times, the inner loop n times each: O(n log n). For n = 16: 4 × 16 = 64.
3. The inner loop depends on the outer one: n + n/2 + n/4 + ... + 1 < 2n. O(n). "log n outside, n inside, so n log n" is the trap here; for n = 1024 the counter ends at 2047, not 10,240.
4. n + m + 100n. The constant 100 is dropped; n and m are independent inputs, so both stay: O(n + m).
5. The loop stops when s reaches √n: O(√n).
6. Every call makes two calls, depth n: 2ⁿ⁺¹ − 1 calls in total, O(2ⁿ) time. Space is O(n) because only one branch is active at a time. Written as 2 * F(n - 1), the same result would take O(n) time.
7. The inner loop runs about n/i times: n/1 + n/2 + ... + n/n = n × (1 + 1/2 + ... + 1/n). The bracket is the harmonic series, roughly ln n: O(n log n).
8. The range halves with every call: T(n) = T(n/2) + O(1), O(log n) time. The recursive version also needs O(log n) space; the iterative BinarySearch above does the same job in O(1) space.

A Small Scenario: Checking for Duplicates

Imagine a registration form where you must check whether a list of incoming numbers contains a duplicate. The first idea is to compare every pair; the second is to keep what you have seen in a HashSet.

static bool HasDuplicateSlow(int[] a)
{
    for (int i = 0; i < a.Length; i++)
        for (int j = i + 1; j < a.Length; j++)
            if (a[i] == a[j]) return true;
    return false;
}

static bool HasDuplicateFast(int[] a)
{
    var seen = new HashSet<int>();
    foreach (int x in a)
        if (!seen.Add(x)) return true; // Add returns false if the element already exists
    return false;
}

The first takes O(n²) time and O(1) space, the second O(n) time on average and O(n) space. This is a typical time-space trade-off: you buy speed with extra memory. Both versions have the same best case (if the first two elements are equal they return immediately); the difference shows in the worst case, when there is no duplicate at all.

When to Use It and When Not To

Big O earns its keep when the input can grow and you are choosing between two approaches: if n can reach millions, the gap between O(n²) and O(n log n) is the gap between code that works and code that does not. Choosing a data structure rests on the same analysis; a binary search tree, for example, searches in O(log n) while balanced and in O(n) once it degenerates.

There are places where it is not enough on its own. For small, bounded n (a ten-item menu list) constant factors decide; an O(n²) insertion sort can beat an O(n log n) merge sort. The notation also says nothing when you compare two algorithms in the same class. The alternative in those cases is measuring: time real data with Stopwatch or a benchmark library. Big O tells you what to measure; it does not replace the measurement.

Common Mistakes

1. Dropping the wrong term. In O(n² + n log n) the dominant term is n², so n log n goes. But in O(n + m) you cannot drop m: it is a separate input and may be larger than n. Likewise, writing O(2n) or O(n/2) is a notation error; both are O(n). The base of a logarithm is a constant factor too: O(log₂ n) and O(log₁₀ n) are the same class.

2. Confusing best case with Ω. Best, average and worst case describe which input you look at; O, Ω and Θ describe which kind of bound you put on that case's function. Insertion sort's best case is Θ(n), its worst case Θ(n²). The sentence "insertion sort is Ω(n)" is true, but it does not mean "best case"; it says every input costs at least n operations.

3. Seeing two loops and saying n². Two loops one after the other are O(n). Even nested loops can come out as n log n or n, as exercises 2, 3 and 7 show. Do not count loops; work out how often the innermost body runs in total.

4. Missing a hidden cost. A method called inside a loop may not be O(1):

for (int i = 0; i < list.Count; i++)
    if (list.Contains(target - list[i])) return true; // Contains is O(n) -> O(n²) overall

List<T>.Contains is a linear search; this code looks like one loop but is O(n²). With a HashSet<T> it drops to O(n) on average.

If you want to practise questions like these on your own course's past papers, have a look at the exam support page.

Frequently Asked Questions

Does Big O always describe the worst case?

No. Big O is an upper-bound notation and can be applied to the best, average or worst case. In practice it is mostly used for the worst case, which is why the two get mixed up.

What is the base of the logarithm in O(n log n)?

Usually 2, because it comes from repeated halving, but for the notation it makes no difference. Different bases differ by a constant factor, and constant factors are dropped in Big O.

Can the Master theorem be applied to every recurrence?

No, only to divide-and-conquer recurrences of the form T(n) = a·T(n/b) + f(n). For recurrences that shrink the problem by subtraction, such as T(n) = T(n−1) + O(1) or Fibonacci, use the call chain or the recursion tree method.

Which matters more, time or space complexity?

It depends. Exams and most applications ask about time first, but when memory is limited or the recursion depth is large, space becomes decisive. A good answer states both.