Big-O Notation: Time and Space Complexity Explained

Two programs can give the same correct answer and still differ by a factor of a million in how long they take. Before you write a solution you want to know whether it will finish inside the time limit — usually a second or two for inputs of up to 10⁵ or 10⁶ items. Time complexity is the tool for that judgement, and Big-O notation is the shorthand everyone uses to state it.

Why count operations, not seconds

Seconds depend on the machine and the language; how the work grows with the input does not. So count basic operations — an addition, a comparison, reading one element — as a function of the input size n. Finding the largest value takes about 2n; comparing every pair for a duplicate takes n(n − 1)/2. At n = 10⁵ that is 2 × 10⁵ against 5 × 10⁹, and a judge does roughly 10⁸ simple operations a second: milliseconds against nearly a minute. No faster machine closes that gap. A better algorithm does.

Big-O: an upper bound on growth

A cost f(n) is O(g(n)) if there are constants c > 0 and n₀ with f(n) ≤ c × g(n) for every n ≥ n₀: beyond some size, f never grows faster than g times a constant.

1. f(n) = 3n² + 5n + 20 is the exact count for some program. It sits above n² everywhere, so "f ≤ n²" is false — but Big-O only asks for n² times some constant, from some size on.
2. Take c = 4: from n₀ = 8 on, f(n) never rises above 4n² again, so f is O(n²). The constant swallows the 3, and the 5n + 20 matters less and less — at n = 1,000 it is under 0.2 per cent of f.

Two everyday rules follow from the definition:

• Drop constant factors. 5n, n/2 and 100n are all O(n); the constant depends on the language and the machine.
• Drop lower-order terms. 3n² + 5n + 20 is O(n²); the smaller terms fade as n grows.

State the smallest bound you can justify: a linear algorithm is technically O(n²) too. Ω is a lower bound and Θ both at once, though interviews use "O" for the tight bound. The worst case is the default, since a judge chooses its tests; the average case is the expected cost over random inputs, as with a hash lookup's O(1) — see Hashing.

The common complexity classes

Almost every algorithm falls into one of a handful of classes:

1. O(1), constant: reading arr[i] or an average hash lookup costs the same at any size. The flat line along the bottom.
2. O(log n), logarithmic: a loop that halves, as in binary search. Doubling n adds one step; a billion items need about 30.
3. O(n), linear: one pass — a sum, a maximum, a running minimum. Doubling n doubles the work; about 10⁸ steps fit in a second.
4. O(n log n): sorting. Slightly more than double when n doubles, and comfortable up to about 10⁶ items.
5. O(n²), quadratic: every pair, two nested loops. Doubling n quadruples the work, so about 10⁴ items is the limit.
6. O(2ⁿ), exponential: every subset. One more item doubles the work — it leaves the chart before n = 6 and tops out near n = 25.

The last column is 10⁸ divided by the cost: rough (Python is about ten times slower) but enough to rule an approach in or out. The base of a logarithm does not matter, since log₂ n and log₁₀ n differ by a constant.

How to work out the complexity of code

Five rules cover nearly all the code you will analyse:

• Sequential blocks add. A loop over n, then one over m, is O(n + m).
• Nested loops multiply. n steps around m steps is O(n × m).
• An inner loop that depends on the outer index still counts fully — see the triangle below.
• A loop that halves or doubles is logarithmic.
• A call costs what it does. n binary searches are O(n log n); n calls to indexOf or Python's in on a list are O(n²).

1. Each square is one run of the inner body, for n = 6. Both loops run n times: n² = 36 runs. Starting j after i skips the diagonal and below: n(n − 1)/2 = 15, a little under half.
2. Double n to 12: the square grows to 144 runs and the triangle to 66 — both about four times bigger. The half changes how long one run takes, never the shape of the growth: both are O(n²).

1. The loop starts with i = 100, runs its body once and sets i to 50. The bar is i: the work left to halve.
2. Run 2 sees i = 50 and halves it to 25. Each run removes half of what is left, not a fixed amount.
3. Run 3: i = 25, halved (rounding down) to 12.
4. Run 4: i = 12, halved (rounding down) to 6.
5. Run 5: i = 6, halved (rounding down) to 3.
6. Run 6: i = 3, halved (rounding down) to 1.
7. Run 7: i = 1, and halving it gives 0, so the test i > 0 fails and the loop ends.
8. 7 runs for n = 100, and log₂ 100 ≈ 6.6. A million needs 20 runs and a billion 30: that is O(log n), and why an O(log n) step inside an O(n) loop costs so little.

A loop that subtracts 2 each time is still linear; only a factor makes it logarithmic. And the while inside a two pointers or sliding window loop is not O(n²): its pointer never moves back, so it moves at most n times in the whole run. Count the total work, not the indentation.

The code

The program counts how many times each loop body runs as n doubles. The halving loop divides with whole numbers — // in Python, Math.floor in JavaScript — because a plain / would produce fractions and keep going.

#include <iomanip>
#include <iostream>
using namespace std;

// Each function runs one loop shape and counts how many times its body runs.
long long singleLoop(int n) {
    long long count = 0;
    for (int i = 0; i < n; i++) count++;              // n steps: O(n)
    return count;
}

long long nestedLoops(int n) {
    long long count = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) count++;          // n * n steps: O(n^2)
    return count;
}

long long pairLoops(int n) {
    long long count = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) count++;      // n(n-1)/2 steps: still O(n^2)
    return count;
}

long long halvingLoop(int n) {
    long long count = 0;
    for (int i = n; i > 0; i /= 2) count++;           // about log2(n) + 1 steps: O(log n)
    return count;
}

int main() {
    cout << setw(6) << "n" << setw(9) << "single" << setw(9) << "nested"
         << setw(9) << "pairs" << setw(9) << "halving" << "\n";
    for (int n : {100, 200, 400, 800}) {
        cout << setw(6) << n << setw(9) << singleLoop(n) << setw(9) << nestedLoops(n)
             << setw(9) << pairLoops(n) << setw(9) << halvingLoop(n) << "\n";
    }
    return 0;
}

public class Main {
    // Each method runs one loop shape and counts how many times its body runs.
    static long singleLoop(int n) {
        long count = 0;
        for (int i = 0; i < n; i++) count++;              // n steps: O(n)
        return count;
    }

    static long nestedLoops(int n) {
        long count = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) count++;          // n * n steps: O(n^2)
        return count;
    }

    static long pairLoops(int n) {
        long count = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) count++;      // n(n-1)/2 steps: still O(n^2)
        return count;
    }

    static long halvingLoop(int n) {
        long count = 0;
        for (int i = n; i > 0; i /= 2) count++;           // about log2(n) + 1 steps: O(log n)
        return count;
    }

    public static void main(String[] args) {
        System.out.println(String.format("%6s%9s%9s%9s%9s", "n", "single", "nested", "pairs", "halving"));
        for (int n : new int[] {100, 200, 400, 800}) {
            System.out.println(String.format("%6d%9d%9d%9d%9d",
                    n, singleLoop(n), nestedLoops(n), pairLoops(n), halvingLoop(n)));
        }
    }
}

# Each function runs one loop shape and counts how many times its body runs.
def single_loop(n):
    count = 0
    for i in range(n):
        count += 1                    # n steps: O(n)
    return count


def nested_loops(n):
    count = 0
    for i in range(n):
        for j in range(n):
            count += 1                # n * n steps: O(n^2)
    return count


def pair_loops(n):
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            count += 1                # n(n-1)/2 steps: still O(n^2)
    return count


def halving_loop(n):
    count = 0
    i = n
    while i > 0:
        count += 1                    # about log2(n) + 1 steps: O(log n)
        i //= 2
    return count


print(f"{'n':>6}{'single':>9}{'nested':>9}{'pairs':>9}{'halving':>9}")
for n in (100, 200, 400, 800):
    print(f"{n:>6}{single_loop(n):>9}{nested_loops(n):>9}{pair_loops(n):>9}{halving_loop(n):>9}")

// Each function runs one loop shape and counts how many times its body runs.
function singleLoop(n) {
  let count = 0;
  for (let i = 0; i < n; i++) count++; // n steps: O(n)
  return count;
}

function nestedLoops(n) {
  let count = 0;
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++) count++; // n * n steps: O(n^2)
  return count;
}

function pairLoops(n) {
  let count = 0;
  for (let i = 0; i < n; i++)
    for (let j = i + 1; j < n; j++) count++; // n(n-1)/2 steps: still O(n^2)
  return count;
}

function halvingLoop(n) {
  let count = 0;
  for (let i = n; i > 0; i = Math.floor(i / 2)) count++; // about log2(n) + 1 steps: O(log n)
  return count;
}

const pad = (value, width) => String(value).padStart(width);
console.log(pad("n", 6) + pad("single", 9) + pad("nested", 9) + pad("pairs", 9) + pad("halving", 9));
for (const n of [100, 200, 400, 800]) {
  console.log(pad(n, 6) + pad(singleLoop(n), 9) + pad(nestedLoops(n), 9) + pad(pairLoops(n), 9) + pad(halvingLoop(n), 9));
}

     n   single   nested    pairs  halving
   100      100    10000     4950        7
   200      200    40000    19900        8
   400      400   160000    79800        9
   800      800   640000   319600       10

As n doubles, the single loop doubles, both quadratic columns quadruple and the halving loop gains one.

Recursion: count the calls

A recursive function costs the number of calls times the work per call. Draw the recursion tree to count them: a recursive sum is a chain of n calls; merge sort has log₂ n levels each handling all n elements, O(n log n). Naive Fibonacci branches twice at almost every call:

1. Each circle is one call fib(k), and every call above 1 makes two more. fib(5) makes 15 calls in all; each extra level roughly doubles the tree.
2. The highlighted calls repeat work already done: fib(3) is computed 2 times and fib(2) 3 times. At n = 50 the tree has about 4 × 10¹⁰ calls — exponential, quoted as O(2ⁿ).
3. Store each answer the first time and a repeat returns at once (highlighted); the greyed subtrees are never called. 9 calls instead of 15, and 99 for fib(50): O(n). That is dynamic programming.

Storing each answer the first time is the core of dynamic programming; the recursion lesson draws these trees in more depth.

Space complexity and the call stack

Space complexity counts the extra memory as n grows: a few variables are O(1), a copy or a hash set O(n), an n × n table O(n²) — at n = 10⁴ about 400 MB, over a judge's usual 256 MB even when the time is fine. The cost people forget is the call stack:

1. sum(i) returns arr[i] + sum(i + 1). Calling sum(0) puts one frame on the call stack — its parameter, its local values and where to return to.
2. sum(0) cannot finish until sum(1) does, so both frames stay. Every pending call keeps its frame: the stack grows by one per level of recursion.
3. At the base case the stack is 6 frames deep — n + 1 for n = 5. The recursion allocates no array, yet uses O(n) memory; the loop version uses O(1).
4. Returns unwind from the top. sum(3) handed back 6 and its frame is gone, so sum(2) can finish with 4 + 6 = 10 and pop off in turn.
5. All frames are gone and sum(0) = 14. Depth is a hard limit as well as a cost: Python stops at 1,000 frames by default, and a recursion 10⁵ deep can crash in any language.

Memory and time are often traded: a hash set turns an O(n²) duplicate check into O(n), and prefix sums store n totals so every range sum costs O(1).

Amortised cost: why appending to an array is O(1)

A dynamic array appends with one write while it has spare room, and copies everything to a bigger block when it is full — one append can cost O(n). The Arrays lesson animates the resizes; judge a whole sequence instead:

That is amortised O(1): a guarantee about the total of any sequence, not an average over random inputs. Any growth factor above 1 gives it — GCC doubles, Java's ArrayList grows by 1.5 — while a fixed increment never does.

The code

The program simulates both growth rules and counts the copies.

#include <iostream>
using namespace std;

// Appends n items to a simulated dynamic array and counts the element copies
// its resizes cost. Doubling starts from 1 slot; the other rule adds 10 slots.
long long copiesForAppends(int n, bool doubling) {
    long long capacity = doubling ? 1 : 10;
    long long size = 0, copies = 0;
    for (int i = 0; i < n; i++) {
        if (size == capacity) {                  // full: move everything to a bigger block
            copies += size;
            capacity = doubling ? capacity * 2 : capacity + 10;
        }
        size++;                                  // the append itself: one write
    }
    return copies;
}

int main() {
    for (int n : {1000, 10000, 100000}) {
        cout << n << " appends: doubling copies " << copiesForAppends(n, true)
             << " elements, adding 10 slots copies " << copiesForAppends(n, false) << "\n";
    }
    return 0;
}

public class Main {
    // Appends n items to a simulated dynamic array and counts the element copies
    // its resizes cost. Doubling starts from 1 slot; the other rule adds 10 slots.
    static long copiesForAppends(int n, boolean doubling) {
        long capacity = doubling ? 1 : 10;
        long size = 0, copies = 0;
        for (int i = 0; i < n; i++) {
            if (size == capacity) {                  // full: move everything to a bigger block
                copies += size;
                capacity = doubling ? capacity * 2 : capacity + 10;
            }
            size++;                                  // the append itself: one write
        }
        return copies;
    }

    public static void main(String[] args) {
        for (int n : new int[] {1000, 10000, 100000}) {
            System.out.println(n + " appends: doubling copies " + copiesForAppends(n, true)
                    + " elements, adding 10 slots copies " + copiesForAppends(n, false));
        }
    }
}

def copies_for_appends(n, doubling):
    """Append n items to a simulated dynamic array and count the element copies
    its resizes cost. Doubling starts from 1 slot; the other rule adds 10 slots."""
    capacity = 1 if doubling else 10
    size = copies = 0
    for i in range(n):
        if size == capacity:                     # full: move everything to a bigger block
            copies += size
            capacity = capacity * 2 if doubling else capacity + 10
        size += 1                                # the append itself: one write
    return copies


for n in (1000, 10000, 100000):
    print(f"{n} appends: doubling copies {copies_for_appends(n, True)} elements, "
          f"adding 10 slots copies {copies_for_appends(n, False)}")

// Appends n items to a simulated dynamic array and counts the element copies
// its resizes cost. Doubling starts from 1 slot; the other rule adds 10 slots.
function copiesForAppends(n, doubling) {
  let capacity = doubling ? 1 : 10;
  let size = 0;
  let copies = 0;
  for (let i = 0; i < n; i++) {
    if (size === capacity) {
      // full: move everything to a bigger block
      copies += size;
      capacity = doubling ? capacity * 2 : capacity + 10;
    }
    size++; // the append itself: one write
  }
  return copies;
}

for (const n of [1000, 10000, 100000]) {
  console.log(`${n} appends: doubling copies ${copiesForAppends(n, true)} elements, adding 10 slots copies ${copiesForAppends(n, false)}`);
}

1000 appends: doubling copies 1023 elements, adding 10 slots copies 49500
10000 appends: doubling copies 16383 elements, adding 10 slots copies 4995000
100000 appends: doubling copies 131071 elements, adding 10 slots copies 499950000

With doubling the copies stay just above n, about one extra write per append. Adding ten slots multiplies the copies by a hundred each time n grows tenfold: quadratic growth.

Read the constraints first

Problem setters choose the input limits so the intended solution passes and the next slower one does not. Before designing anything, look at the largest n and work back from about 10⁸ operations:

So n ≤ 10⁵ says O(n²), 10¹⁰ steps, is meant to fail. Read the limits on the values too: values up to 10⁹ mean a sum of two can pass the 32-bit limit.

Hidden costs in everyday code

Common mistakes

• A library call as one step. x in my_list inside a loop over that list is O(n²).
• Forgetting the sort. "Sort, then one pass" is O(n log n).
• One n for two inputs. Sizes n and m give O(n + m) or O(n × m).
• Every nested loop as O(n²). A pointer that never moves back is O(n) in total.
• Ignoring the call stack. Deep recursion uses O(depth) memory, and can crash.
• Big-O alone for small inputs. At n = 100 a plain O(n²) loop can beat a hashing O(n) one.

Practice in this order

Write down the slow and the fast complexity of each before you code:

1. Running Sum of 1d Array: reuse the previous total.
2. Concatenation of Array: an output that is not extra space.
3. Contains Duplicate: O(n²), O(n log n), then O(n).
4. Missing Number: O(1) space with the sum formula.
5. Two Sum: every pair against one hash map pass.
6. Find Pivot Index: running totals instead of rescans.
7. Best Time to Buy and Sell Stock: a running minimum.
8. Maximum Subarray: from O(n³) down to O(n).

The array problem list has many more. The next lesson, Arrays, puts these costs to work on the data structure every other stage is built on.