How to Explain Big O Notation in Interviews: A Step-by-Step Guide

Most technical interviews for software engineers involve questions about Big O notation.

Typically this happens after coding your solution, when you'll be asked about its time and space complexity. How you analyze and communicate this can be just as important as the solution itself.

In this blog post we'll break down how to best answer it clearly and effectively.

A Four-Step Approach

When discussing time or space complexity during an interview, structure your explanation with these four steps:

1. State the Time and Space Complexity upfront

• Use Big O notation
• Focus on the worst-case scenario at this stage

2. Break down the algorithm

• Time complexity:
  • Walk through the key operations (loops, recursion, etc.)
  • Identify the most significant term
• Space complexity:
  • Highlight the key data structures and recursion stack that contribute to memory usage
  • Identify the most significant term

3. Mention best / average cases (optional)

• Focus on worst-case complexity first, but acknowledge best and average cases when relevant (see misconception 3)

4. Tie it back to real-world implications

• Discuss how the complexity scales with input size
• Talk about how a modern cloud infrastructure could handle the scale of the algorithm in real life (see misconceptions 1 and 5)
• Mention any possible trade-offs and optimizations

Examples

Let's use a couple of examples to illustrate this approach.

Example 1: Array Manipulation

1. State the Time and Space Complexity upfront

"This solution has a worst-case time complexity of O(n) and a space complexity of O(n)"

2. Break down the algorithm

"There is a single loop going through the array, where for each element it:
• calculates the complement (O(1))
• checks if it exists in the Set (O(1))
• adds the current number to the Set (O(1))

Since all operations inside the loop are O(1), and they are done n times, the overall time complexity is O(n)."

"For space complexity, the algorithm is using:
• A Set to store the numbers we've seen, which could grow to size n
• An array to store the pairs, which in the worst case could be n/2 pairs

Both of these scale linearly with input size, so our space complexity is O(n)."

3. Mention best / average cases (optional)

Skip this step since best and average complexities are not particularly relevant for this algorithm

4. Tie it back to real-world implications

"This solution is efficient for finding pairs. It scales linearly with the input size, and could easily scale with modern cloud infrastructure."

"I can't think of any optimizations that would significantly improve the time or space complexity of this solution."

Example 2: Matrix Traversal

1. State the Time and Space Complexity upfront

"This solution has a time complexity of O(n²) where n is the size of the matrix, and a space complexity of O(1)."

2. Break down the algorithm

"Let's break down the time complexity:
• The first operation uses nested loops, its worst-case time complexity is O(n²) even though the second loop starts at i.
• Similarly, whe second operation is also a nested loop, with the inner loop going to n/2. This is also O(n²).
• Since both operations are O(n²) and we do them sequentially, the overall time complexity is O(n²)."

"For space complexity, we're modifying the matrix in place without any additional data structures. Therefore, the space complexity is O(1)"

3. Mention best / average cases (optional)

Skip this step since best and average complexities are not particularly relevant for this algorithm

4. Tie it back to real-world implications

"This solution is very performant when it comes down to space. On the other hand, the time complexity is O(n²), which could be a bottleneck for large matrices. There are no significant optimizations that would improve the time complexity. In the real world, one might consider a different approach for large matrices by marking them as rotated and performing the rotation only when needed."

Tips for Better Complexity Discussion

1. Be Proactive: Don't wait for the interviewer to ask about every aspect. Cover time complexity, space complexity, and any significant trade-offs.

2. Explain: Walk the interviewer through your thinking. Don't simply state the complexity without any explanations.

3. Reference Specific Code: Point to specific parts of your code when explaining complexity.

4. Acknowledge Trade-offs: Show you understand the implications.

5. Be aware of common misconceptions about Big O.

6. Tie it back to the real world: Discuss how the complexity would scale with real-world inputs and infrastructure.