Estimating big O is a crucial part of software engineering interviews. If you can write decent code, but can’t analyze big O, interviewers will mentally subtract points from your score.

Tips for analyzing Big O

• Consider the worst case
• Think about when n is very large. 2^n dwarfs O(n^2)
• Drop constants (e.g. O(2n) -> O(n))

Quick Test

Here’s a quick test (answers at the bottom). For each question, write down the big O runtime of run(…).

Question 1

public int run(int[] input) {
  if (input.length < 1000) {
    return -1;
  }
  for (i = 0; i < 1000; ++i) {
    input[i] = input[i] + 1;
  }
  return 0;
}

Question 2

public void run(int[] input) {
  for (i = 0; i < input.length; ++i) {
    input[i] = input[i] + 1;
  }
}

Question 3

public void run(int[] input) {
  for (i = 0; i < input.length; i += 2) {
    input[i] = input[i] + 2;
  }
}

Question 4

public int run(int[][] input) {
  int sum = 0;
  for (i = 0; i < input.length; ++i) {
    for (j = 0; j < input[i].length; ++j) {
      sum += input[i][j];
    }
  }
  return sum;
}

Question 5

// Return a random number between 0 and m-1
public int random(int m); // O(1)

public int run(int[] input, int k) {
  int index = random(input.length);
  input[index] = input[0];
  if (k < 0) {
    return 1;
  }
  return run(input, k - 1) + 1;
}

Question 6

// Return a random number between 0 and m-1
public int random(int m); // O(1)

public int run(int[] input) {
  return inner(input, input.length - 1);
}

public int inner(int[] input, int i) {
  int foo = random(10);
  input[i] += foo;
  if (i < 0) {
    return 1;
  }
  return inner(input, i - 1) + inner(input, i - 2) + 1;
}

Question 7

// Return a random number between 0 and m-1
public int random(int m); // O(1)

public int run(int n) {
  int[] input = new int[n]; // Initialized to all 0s
  return inner(input, n - 1);
}

public int inner(int[] input, int i) {
  if (i < 0) {
    return 0;
  } else if (input[i] > 0) {
    return input[i];
  }
  input[i] = random(10);
  return inner(input, i - 1) + inner(input, i - 2);
}

The answers are below this photo of young Alan Turing.

Answers

1. O(1). When n is large, the runtime is the same as when n is small (max 1000 iterations).
2. O(n). Directly based on input.length
3. O(n). Based on input.length. O(n/2) is equivalent to O(n)
4. O(n^2). The outer loop is executed n times. What does each iteration of the outer loop do? It executes the inner loop n times.
5. O(k). You could also say “O(n), where n is k”. The important thing is that the number of times the function is called is based on k. Executing one stack frame of run(…) is constant time.
6. O(2^n). The runtime is like the number of nodes in a binary tree with n levels. The recursive function causes big O to grow exponentially. The branching factor is 2 because each stack frame calls inner(…) twice.
7. O(n). input acts as a cache that limits the number of calls to inner(…). The recursive function only branches when input[i] <= 0. Therefore, the number of function calls is proportional to input’s length.

How many did you get right?

0-4 – I recommend brushing up on the basics of big O.

5-6 – You’re on a solid path. Keep practicing so you don’t trip up in an interview.

7 – Perfect score! Now’s the time to level up your practice with other data structures like trees and graphs.