The Big‑O Notation: How to Explain It in an Interview (2026)

When interviewers ask about Big‑O, they want to see that you can reason about performance, not just recite a definition. A strong answer is short, grounded in a concrete algorithm, and anticipates the next question.

One‑sentence definition

"Big‑O notation describes the upper bound on how the running time (or memory usage) of an algorithm grows as the size of its input increases."

Why we use the upper bound

• Predictability – Hiring managers care about worst‑case behavior because it guarantees a ceiling on latency.
• Hardware‑agnostic – By abstracting away constant factors, we can compare algorithms independent of CPU speed or compiler optimizations.
• Scalability insight – It tells you how an approach will behave when the data set grows from hundreds to millions of items.

The mechanism behind the notation

1. Identify the basic operation (e.g., a comparison, a memory access).
2. Count how many times that operation executes as a function of n (the input size).
3. Drop lower‑order terms and constant multipliers because they become insignificant for large n.

Example: If a loop runs n times and inside it another loop runs n/2 times, the total operations are roughly n × n/2 = 0.5 n². After discarding the constant 0.5, the complexity is O(n²).

A concrete example: Merge sort

Merge sort splits the array in half recursively, then merges the sorted halves. The recurrence is T(n) = 2·T(n/2) + O(n). Solving it yields T(n) = O(n log n).

Step‑by‑step walk‑through

• Divide – The array is split into two halves until each sub‑array has one element. This creates a recursion depth of log₂ n.
• Conquer – Merging two sorted sub‑arrays of total size n takes linear time, O(n).
• Combine – At each level of recursion we do O(n) work, and there are log n levels, so the total is O(n log n).

Quick comparison table

Typical interview follow‑up questions

60‑second spoken version

"Big‑O tells you how an algorithm’s runtime scales with input size. We focus on the worst‑case because it guarantees a ceiling on latency. For example, merge sort splits the array recursively, giving a recursion depth of log n, and each level does linear work, so the total work is n log n, or O(n log n). This is faster than quadratic approaches like insertion sort, which does O(n²) work. Interviewers often follow up by asking about best‑case, space trade‑offs, or how the algorithm behaves on already‑sorted data. Knowing those nuances lets you pick the right tool for the job."

How to practice this

1. Write the definition on a sticky note and rehearse it until you can say it fluently.
2. Pick three sorting algorithms (e.g., insertion, merge, quick) and derive their Big‑O on paper, then explain the derivation out loud.
3. Use Call Assistant to record yourself answering the 60‑second prompt, then listen back to ensure you stay within the time limit and keep the answer focused.

---

FAQ

• What does the “O” in Big‑O stand for? It stands for “order of,” indicating the growth order of a function as input size becomes large.
• Is Big‑O only about time? No, it can describe space (memory) usage as well; we often talk about O(n) space for algorithms that need extra storage proportional to input size.
• Why ignore constant factors? Because they depend on hardware and implementation details, while the growth rate captures the algorithm’s inherent scalability.
• Can an algorithm have multiple Big‑O classifications? Yes, an algorithm may have different complexities for best, average, and worst cases; interviewers usually ask for the worst‑case unless they specify otherwise.