Time and space complexity

The table from the last lesson had a column called "time grows like". It said n × n for the pair check and n for the Set. In this lesson that column gets its real name, Big O.

After your code runs, the interviewer asks for its time and space complexity. This lesson teaches you to answer for any code you write.

Count steps, not seconds

Run the same code on an old laptop and a new one. The old one might take 2 seconds, the new one 1 second. Seconds describe the machine, not the code.

The number of steps is the same on every machine. So we count steps, and ask one question: how does the count grow when the input grows?

Big O is the answer, written as a formula of n, the input size.

• O(n): double the input, double the work.
• O(n²): double the input, four times the work.

Always the worst case

Big O describes the input that makes your code work hardest.

• The Set check from the last lesson can stop at the second item, if the duplicate is there.
• When nothing repeats, it reads all n items.
• So the Set check is O(n).

You plan for the input that hurts, not the lucky one.

Keep the biggest term, drop the constant

Counting every step gives a long formula. Two rules turn it into Big O:

1. Keep the biggest term. For large n, it is the only one that matters.
2. Drop the constant in front. 3n² and n² grow the same way.

┌───────────────────────────────────────────────┐
│                                               │
│   steps = 3n² + 5n + 2                        │
│           ─┬─   ─┬   ┬                        │
│            │     │   └─ fixed setup: drop     │
│            │     └───── grows slower: drop    │
│            └─────────── grows fastest: keep   │
│                                               │
│   Big O = O(n²)                               │
│                                               │
└───────────────────────────────────────────────┘

Why drop so much? Take n = 1,000:

• 3n² is 3,000,000.
• 5n + 2 is only 5,002, less than 0.2 percent of the total.

The constant goes for a similar reason. Double n, and both 3n² and n² grow four times. Big O records that growth, not the exact count.

Read the loops

Most of the time, the shape of the loops tells you the Big O. Four shapes cover most code.

Constant: O(1)

JavaPythonTypeScript

int first(int[] nums) {
    return nums[0];
}

One step at any size. Reading an index and a Set lookup are O(1) too.

Linear: O(n)

JavaPythonTypeScript

long total(int[] nums) {
    long sum = 0;
    for (int x : nums) sum += x;
    return sum;
}

The loop body runs once per item, so n items take n steps. Two loops one after the other take n + n = 2n steps. Drop the 2: still O(n).

• In Java, the sum is a long. An int stops at 2,147,483,647, and three values of 10⁹ already pass it.
• In Python, the sum is named s, so it does not hide the built-in sum() function.

Nested: O(n²)

JavaPythonTypeScript

long countPairs(int[] nums) {
    long pairs = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) pairs++;
    }
    return pairs;
}

This is the pair check from the last lesson. Count it out loud:

• When i is 0, j runs n − 1 times.
• When i is 1, j runs n − 2 times.
• And so on, down to 0 times for the last item.

┌────────────────────────────────────────────┐
│                                            │
│                 j = 0  1  2  3  4          │
│         i = 0       ·  ×  ×  ×  ×          │
│         i = 1       ·  ·  ×  ×  ×          │
│         i = 2       ·  ·  ·  ×  ×          │
│         i = 3       ·  ·  ·  ·  ×          │
│         i = 4       ·  ·  ·  ·  ·          │
│                                            │
└────────────────────────────────────────────┘

The pairs fill about half of an n × n square: n × (n − 1) / 2 steps. Keep n², drop the half. A loop inside a loop over the same input is O(n²).

In Java, pairs is a long: for n = 100,000 the count is 4,999,950,000, past the int limit.

Halving: O(log n)

JavaPythonTypeScript

int halvings(int n) {
    int left = n;
    int steps = 0;
    while (left > 1) {
        left = left / 2;
        steps++;
    }
    return steps;
}

• Each pass cuts the work in half, so the loop ends fast.
• Each language drops the fraction its own way. Java's / on two ints does it. Python needs //, because / gives a float such as 3.5. TypeScript needs Math.floor.

┌────────────────────────────────────────────┐
│                                            │
│            16  ████████████████            │
│             8  ████████                    │
│             4  ████                        │
│             2  ██                          │
│             1  █                           │
│                                            │
└────────────────────────────────────────────┘

The number of halvings is log n. halvings(1_000_000) returns 19, so even a million items take about 20 steps.

Binary search works this way. You will meet it in a few weeks.

What fits in one second

A rough rule from coding contests: an online judge runs about 10⁸ (100 million) simple steps per second. Use it to check an idea before you code it.

A time limit of 2 seconds allows about 2 × 10⁸ steps. Double the time, double the steps.

Put the largest n into your Big O before you code. When n can be 100,000, an O(n²) answer takes 10¹⁰ steps. That is 100 times the budget, so you need O(n log n) or better:

Space: the memory you add

Your code uses two kinds of memory:

• Input space: the memory the input takes. You were given it.
• Extra space: the memory your code adds, such as variables, a copy or a Set. It is also called auxiliary space.

Space complexity in an interview usually means the extra space, in the same Big O terms. Most interviewers do not count the output either.

Faster code often pays with memory. The next problem shows that trade.

One problem, two ways

Think of a sales dashboard. You drag across a range of days, and it shows the total for that range.

Here q is the number of queries. Both n and q can reach 100,000.

Brute force: add up each range

For each query, walk from l to r and add.

JavaPythonTypeScript

long[] rangeSums(int[] nums, int[][] queries) {
    long[] answers = new long[queries.length];
    for (int k = 0; k < queries.length; k++) {
        int l = queries[k][0], r = queries[k][1];
        long sum = 0;
        for (int i = l; i <= r; i++) sum += nums[i];
        answers[k] = sum;
    }
    return answers;
}

Count the cost:

• The outer loop runs q times.
• The inner loop reads up to n items each time.
• So time is O(n × q), and extra space is O(1).

At the limits, that is 100,000 × 100,000 = 10 billion steps. Far too slow.

Best: build running totals once

The waste: every query adds the same items again. So add them once.

Build a prefix sum array. prefix[i] holds the sum of the first i items, so prefix[0] is 0.

The sum from l to r is everything up to r, minus everything before l:

• For [1, 3]: the first 4 items add up to 10. The first item alone is 2.
• So the answer is 10 − 2 = 8, in one subtraction.

JavaPythonTypeScript

long[] rangeSums(int[] nums, int[][] queries) {
    long[] prefix = new long[nums.length + 1];
    for (int i = 0; i < nums.length; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    long[] answers = new long[queries.length];
    for (int k = 0; k < queries.length; k++) {
        int l = queries[k][0], r = queries[k][1];
        answers[k] = prefix[r + 1] - prefix[l];
    }
    return answers;
}

• The first loop adds the next item to the last running total.
• The last part answers each query with prefix[r + 1] - prefix[l]: a loop in Java, a list comprehension in Python, map in TypeScript.
• In Java, prefix holds long values. 10⁵ items of 10⁹ add up to 10¹⁴, far past the int limit.
• Building the prefix is O(n). The q queries are O(q). So time is O(n + q), and the prefix costs O(n) extra space.

Side by side

You trade n extra numbers in memory for a speed-up of 50,000 times. That is almost always a good deal.

take U forwardYouTube

Read more

• Big-O cheat sheet, the common classes and data structure costs on one page
• Reconciliation in the React docs, the O(n³) problem and React's O(n) shortcut
• Prefix sum on Wikipedia, with more uses of running totals
• Big O notation on Wikipedia, the formal definition for when you want the maths

Next: how to read a problem statement, and the questions to ask before you write any code.