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

- O(1). When n is large, the runtime is the same as when n is small (max 1000 iterations).
- O(n). Directly based on input.length
- O(n). Based on input.length. O(n/2) is equivalent to O(n)
- 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.
- 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.
- 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.
- 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.