Time and Space Complexity Without the Confusion

"How fast is your solution?" is the question interviewers ask after every answer. If your reply is "it ran in 0.3 seconds on my laptop", you have told them almost nothing. A different machine, a smaller test, or a busy computer would give a different number.

What does stay the same across machines is how the amount of work grows when the input grows. Double the input: does the work double, quadruple, or barely change? That growth is what complexity describes, and it is simpler than it sounds. You are going to count steps.

• How to count steps as a function of the input size n.
• What Big O means, and the three rules for simplifying an expression.
• The common growth rates, and what each looks like in code.
• Best, average and worst case, with a concrete example.
• How to count space, including the recursion stack.
• How to read a piece of code and state its complexity.

Let n be the size of the input, for example the length of an array. A step is one small unit of work: comparing two numbers, reading an array element, adding two values.

Look at three loops:

loop A:  for i in 0..n-1:  do one step              → n stepsloop B:  for i in 0..n-1, for j in 0..n-1:  one step → n × n stepsloop C:  one step, regardless of n                  → 1 step

If n is 1,000, loop A does 1,000 steps, loop B does 1,000,000 and loop C does 1. If n becomes 2,000, loop A does 2,000 steps (double), loop B does 4,000,000 (four times as much) and loop C still does 1. The way each count changes as n changes is its growth rate, and it is what we care about.

Here is a program that counts the steps of several loop shapes for n = 10, 100 and 1000. The only thing it does is count.

// File: Main.javapublic class Main {    static long constantWork(int n) {        return 1;                                   // ignores n completely    }    static long logarithmicWork(int n) {        long steps = 0;        for (int i = 1; i < n; i *= 2) {            // i doubles each time            steps++;        }        return steps;    }    static long linearWork(int n) {        long steps = 0;        for (int i = 0; i < n; i++) {            steps++;        }        return steps;    }    static long linearithmicWork(int n) {        long steps = 0;        for (int i = 0; i < n; i++) {               // n times ...            for (int j = 1; j < n; j *= 2) {        // ... a doubling loop                steps++;            }        }        return steps;    }    static long quadraticWork(int n) {        long steps = 0;        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                steps++;            }        }        return steps;    }    static long triangularWork(int n) {        long steps = 0;        for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {       // inner loop starts after i                steps++;            }        }        return steps;    }    static long fibCalls(int n) {                   // naive recursion: counts the calls made        if (n <= 1) {            return 1;        }        return 1 + fibCalls(n - 1) + fibCalls(n - 2);    }    public static void main(String[] args) {        System.out.println("n        1   log n       n   n log n         n^2   n(n-1)/2");        int[] sizes = {10, 100, 1000};        for (int n : sizes) {            System.out.printf("%-6d %3d %7d %7d %9d %11d %10d%n", n, constantWork(n), logarithmicWork(n),                    linearWork(n), linearithmicWork(n), quadraticWork(n), triangularWork(n));        }        for (int n : new int[] {10, 20, 30}) {            System.out.println("fib(" + n + ") makes " + fibCalls(n) + " calls");        }    }}

n        1   log n       n   n log n         n^2   n(n-1)/210       1       4      10        40         100         45100      1       7     100       700       10000       49501000     1      10    1000     10000     1000000     499500fib(10) makes 177 callsfib(20) makes 21891 callsfib(30) makes 2692537 calls

Read this table slowly. When n grows from 10 to 1,000 (a hundred times bigger):

• The constant column stays at 1.
• The logarithmic column grows from 4 to 10. It barely moves.
• The linear column grows a hundred times.
• The n log n column grows 250 times.
• The quadratic column grows ten thousand times.
• The recursion-based column explodes. Going from n = 20 to n = 30 multiplies the work by more than a hundred.

This is the whole story of complexity, in one table.

You should be able to count simple loops on paper. Take triangularWork(5):

The total is 4 + 3 + 2 + 1 + 0 = 10, which equals 5 × 4 / 2. In general this sum is n × (n - 1) / 2. That is about half of n × n, so it grows like n^2.

And the doubling loop for (int i = 1; i < 20; i *= 2):

It runs 5 times. If you keep doubling until you pass n, the number of iterations is about the number of times you can double 1 before reaching n. That count is what mathematicians call log2(n). We just call it "log n" and treat it as "the number of times you can halve n before reaching 1". Binary search, which we see in Searching and Sorting, works this way.

Big O notation describes how the step count grows, ignoring details that do not matter when n is large. Formally, saying a step count f(n) is O(g(n)) means that for large enough n, f(n) stays below some constant multiple of g(n). In practice, use these rules.

1. Drop constant factors. 3n steps and 100n steps are both O(n). Doubling the speed of a machine changes a constant factor, not the shape of growth.
2. Drop lower-order terms. n^2 + 5n + 40 is O(n^2). When n is a million, n^2 is a trillion and 5n is five million, which is noise.
3. Keep different inputs separate. If a method takes two arrays of sizes a and b and does a × b work, it is O(a × b), not O(n^2). If it processes one after the other, it is O(a + b).

Two more combining rules:

• Steps in sequence add. A loop of n steps followed by a loop of n^2 steps is O(n + n^2) = O(n^2).
• Steps nested multiply. A loop of n iterations containing a loop of m iterations is O(n × m).

Worked example. For this code:

for (int i = 0; i < n; i++) {          // n times    total += values[i];                // 1 step}for (int i = 0; i < n; i++) {          // n times    for (int j = 0; j < n; j++) {      // n times each        count++;                       // 1 step    }}

The first loop costs n and the second costs n^2. The total is n + n^2, and we keep the dominant term, so the code is O(n^2).

How large can n be before each one is too slow? Use the rough guide from Problem Solving Fundamentals: O(n^2) is usually fine for n up to a few thousand, O(n log n) and O(n) for n up to hundreds of thousands or millions, O(2^n) only up to about 20 or 25, and O(n!) only up to about 10.

The exponential row of our program shows why. Naive Fibonacci with n = 30 makes 2,692,537 calls. At n = 50 it would make about 40 billion. We fix this with dynamic programming in Dynamic Programming: Learn to Recognize Overlapping Subproblems.

The same algorithm can do different amounts of work for different inputs of the same size. That is why complexity is attached to a case.

Take linear search: look through an array until you find the target.

// File: Main.javapublic class Main {    static int comparisons(int[] a, int target) {        int count = 0;        for (int value : a) {            count++;            if (value == target) {                return count;            }        }        return count;    }    public static void main(String[] args) {        int n = 1000;        int[] a = new int[n];        for (int i = 0; i < n; i++) {            a[i] = i;        }        System.out.println("best (first element): " + comparisons(a, 0));        System.out.println("worst (last element): " + comparisons(a, n - 1));        System.out.println("worst (missing):      " + comparisons(a, -1));        long total = 0;        for (int target = 0; target < n; target++) {            total += comparisons(a, target);        }        System.out.println("average over all present targets: " + (double) total / n);    }}

best (first element): 1worst (last element): 1000worst (missing):      1000average over all present targets: 500.5

• Best case: the target is the first element, so one comparison, O(1).
• Worst case: the target is last or missing, so n comparisons, O(n).
• Average case: if the target is equally likely to be anywhere, about n / 2 comparisons, which is still O(n).

By default, when someone asks "what is the complexity?", give the worst case, because it is a guarantee. Mention the others when they differ meaningfully. For example, quicksort is O(n log n) on average but O(n^2) in its worst case, and a hash table lookup is O(1) on average but can degrade in the worst case.

Some operations are usually cheap and occasionally expensive. An ArrayList is backed by an array. When the array is full, add allocates a bigger one and copies everything over. A single add can cost O(n), yet a long series of adds is cheap per element. We call that amortized O(1). This small program counts the copies for a list that doubles its capacity each time it is full:

// File: Main.javapublic class Main {    public static void main(String[] args) {        int capacity = 1;        int size = 0;        long copies = 0;        int n = 1000;        for (int i = 0; i < n; i++) {            if (size == capacity) {                copies += size;      // every existing element is copied to the bigger array                capacity *= 2;            }            size++;        }        System.out.println("added " + n + " elements, copied " + copies + " in total, capacity " + capacity);    }}

added 1000 elements, copied 1023 in total, capacity 1024

Adding 1,000 elements caused 1,023 copies in total. The copies cost 1 + 2 + 4 + ... + 512, which is always less than twice the final size, so the average extra cost per add is a constant. (Java's ArrayList grows by a smaller factor than 2, but the reasoning is the same.)

Space complexity measures how much extra memory your algorithm uses as n grows. We usually count the auxiliary space: the additional memory beyond the input itself.

Every recursive call that has not yet returned takes a little memory on the call stack. A recursive method that goes n levels deep before returning uses O(n) space even if it creates no arrays. A method that halves the problem at each call, like binary search, goes only O(log n) deep. Java also has a limit on how deep the stack can grow, so very deep recursion fails with a StackOverflowError. We investigate this in Recursion and Backtracking.

In the very first article, hasDuplicateSet was much faster than the brute force, but it used O(n) extra space for the set while the brute force used O(1). This kind of trade, spending memory to save time, shows up in hashing, prefix sums and dynamic programming. Always ask yourself which resource is scarcer for the problem at hand.

Use this procedure on any piece of code:

1. Identify what n is. If there are several independent inputs, give them separate names.
2. Find the loops and recursive calls.
3. For each loop, ask how many times it runs, in terms of n.
4. Add the costs of code in sequence. Multiply the costs of nested code.
5. Look for hidden costs inside library calls.
6. Drop constants and lower-order terms.

Let us practise on a few shapes.

A. Two sequential loops

for (int i = 0; i < n; i++) { ... }for (int j = 0; j < n; j++) { ... }

n + n = 2n, so O(n).

B. A loop inside a loop where the inner one shrinks

for (int i = 0; i < n; i++) {    for (int j = i + 1; j < n; j++) { ... }}

This is the triangular sum, n × (n - 1) / 2, so O(n^2).

C. A loop whose counter doubles, inside a loop that runs n times

for (int i = 0; i < n; i++) {    for (int j = 1; j < n; j *= 2) { ... }}

n × log n, so O(n log n). It matches the "n log n" column in the table.

D. Hidden costs

for (int i = 0; i < n; i++) {    if (list.contains(values[i])) { ... }   // contains walks the list: O(n)}

The loop runs n times and list.contains is itself O(n), so the code is O(n^2) even though there is only one loop in sight. Using a HashSet instead makes each check O(1) on average, and the whole thing O(n).

For recursion, think of the recursion tree: each call is a node, and its recursive calls are its children. The total work is the sum of work over all nodes.

The last row is merge sort. The second-to-last row is naive Fibonacci, which is why 30 gave 2.7 million calls. We use this tree thinking again in the recursion, sorting and dynamic programming articles.

• Confusing the input size. For a method that takes a string of length m and an array of length n, say so. Do not call both n without saying so.
• Forgetting hidden costs. String concatenation in a loop, list.remove(0), list.contains, substring and equals on long strings are all not O(1).
• Calling a nested loop O(n^2) when the bounds differ. If the inner loop runs a fixed 26 times (the alphabet), the total is O(26 n) = O(n).
• Ignoring space. An answer that is fast but needs O(n^2) memory may crash for large inputs.
• Believing O(n) is always faster than O(n log n). For small n, or with a large constant factor, it may not be. Big O describes growth. It does not tell you the winner for every n.
• Treating the number itself as the size. For a function like isPrime(n), the loop to sqrt(n) is fast in terms of the value of n, but the size of the input in bits is only about log n. This subtlety matters for some theory topics, and it explains why dynamic programming solutions that loop up to a target value are called pseudo-polynomial. You do not need it yet.
• Mixing up Big O with best case. Big O is not "best case". It is an upper bound that can describe any case.

for (int i = 0; i < n; i++) {    for (int j = i; j < n; j++) {        count++;    }}

// (a)for (int i = 0; i < n; i += 2) { work(); }// (b)for (int i = n; i > 0; i /= 2) { work(); }// (c)for (int i = 0; i < n; i++) {    for (int j = 0; j < n; j++) {        for (int k = 0; k < 10; k++) { work(); }    }}// (d)for (int i = 0; i < a; i++) {    for (int j = 0; j < b; j++) { work(); }}// (e)void f(int n) {    if (n == 0) return;    f(n - 1);    f(n - 1);}

static String joinWithCommas(List<Integer> values) {    String result = "";    for (int v : values) {        result += v + ",";    }    return result;}static List<Integer> dedupe(List<Integer> values) {    List<Integer> result = new ArrayList<>();    for (int v : values) {        if (!result.contains(v)) {            result.add(v);        }    }    return result;}static long drain(List<Integer> values) {    long sum = 0;    while (!values.isEmpty()) {        sum += values.remove(0);    }    return sum;}

// File: Main.javaimport java.util.ArrayList;import java.util.HashSet;import java.util.List;import java.util.Set;public class Main {    static String joinSlow(List<Integer> values) {        String result = "";        for (int v : values) {            result += v + ",";        }        return result;    }    static String joinFast(List<Integer> values) {        StringBuilder result = new StringBuilder();        for (int v : values) {            result.append(v).append(',');        }        return result.toString();    }    static List<Integer> dedupeSlow(List<Integer> values) {        List<Integer> result = new ArrayList<>();        for (int v : values) {            if (!result.contains(v)) {                result.add(v);            }        }        return result;    }    static List<Integer> dedupeFast(List<Integer> values) {        Set<Integer> seen = new HashSet<>();        List<Integer> result = new ArrayList<>();        for (int v : values) {            if (seen.add(v)) {          // add returns false if the value was already present                result.add(v);            }        }        return result;    }    static long drainSlow(List<Integer> values) {        List<Integer> copy = new ArrayList<>(values);        long sum = 0;        while (!copy.isEmpty()) {            sum += copy.remove(0);        }        return sum;    }    static long drainFast(List<Integer> values) {        long sum = 0;        for (int v : values) {            sum += v;        }        return sum;    }    public static void main(String[] args) {        List<Integer> sample = List.of(4, 8, 4, 15, 8, 16, 23, 42);        System.out.println(joinSlow(sample).equals(joinFast(sample)) + " " + joinFast(sample));        System.out.println(dedupeSlow(sample).equals(dedupeFast(sample)) + " " + dedupeFast(sample));        System.out.println((drainSlow(sample) == drainFast(sample)) + " " + drainFast(sample));    }}

true 4,8,4,15,8,16,23,42,true [4, 8, 15, 16, 23, 42]true 120

• Next: Arrays and Array-Based Problem Solving starts the data-structures module, and puts complexity to work at once.
• Revisit later: the table in this article is useful at every step. Come back to it when you meet sorting, hashing and dynamic programming.
• Practice habit: from now on, state the time and space complexity of every solution you write, in a comment above the method.