LiveCodingInterview.com
← Articles

How to Analyze Time Complexity in Coding Interviews

Nearly every coding interview ends with: "What's the time complexity?" You are not being asked to count CPU cycles. Interviewers want to know whether your approach scales — and whether you can spot bottlenecks before they become bugs in production.

Big O describes how runtime grows as input size grows. It ignores constants and lower-order terms, which is why O(3n + 50) is still O(n). If you can state complexity confidently and tie it back to your code structure, you signal senior-level thinking even on medium problems.

What Big O actually means

We write O(f(n)) to say: "For large enough input, runtime grows no faster than f(n)." The variable n almost always means the primary input size — array length, string length, number of nodes. When two inputs matter (a grid with n rows and m columns), use both: O(nm).

Interview tip: always define n out loud before analyzing. "Let n be the number of users in the feed" removes ambiguity and buys you a few seconds to think.

Reading loops

Loops are the fastest way to estimate complexity. Count how many times the innermost work runs relative to n.

**Single pass — O(n).** One loop over the input:

for (let i = 0; i < nums.length; i++) {
  // constant work
}

**Nested loops — O(n²).** Every element paired with every other element:

for (let i = 0; i < nums.length; i++) {
  for (let j = 0; j < nums.length; j++) {
    // constant work
  }
}

**Triangle loop — still O(n²).** The inner loop starts at i, not 0, but you still iterate roughly n²/2 times:

for (let i = 0; i < nums.length; i++) {
  for (let j = i + 1; j < nums.length; j++) {
    // compare pairs
  }
}

Rule of thumb: k nested loops that each scale with n → O(n^k). Three nested loops over n → O(n³).

Constants do not change Big O

These loops all look different but are all O(n):

for (let i = 0; i < 3 * n; i++) { /* ... */ }
for (let i = 0; i < n + 100; i++) { /* ... */ }
for (let i = 0; i < n; i += 2) { /* ... */ }

Interviewers care about growth rate, not whether you loop 2n or 5n times. Drop constants when you speak: say O(n), not O(2n).

Multiple passes add, but watch the max

When code runs in sequential phases, the slowest phase dominates.

function process(nums) {
  nums.forEach(() => { /* O(n) */ });

  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length; j++) {
      /* O(n²) */
    }
  }

  nums.sort(); // O(n log n)
}

Total: O(n) + O(n²) + O(n log n) = **O(n²)**. The quadratic nested loop is the bottleneck. Mention that explicitly — it shows you know which line matters.

Two inputs: use two variables

Grids, graphs, and string matching often depend on two dimensions:

for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    // visit cell (i, j)
  }
}

Complexity is **O(nm)**, not O(n²), unless m and n are the same. For a square grid, say O(n²). For comparing two strings of length n and m, many DP solutions are O(nm).

Recursion: multiply calls × work per call

Recursive runtime = (number of calls) × (work per call, excluding deeper recursion).

**Linear recursion — O(n).** One recursive call per level:

function countdown(n) {
  if (n === 0) return;
  countdown(n - 1);
}

n calls, O(1) each → O(n).

**Binary recursion — O(2^n).** Two calls branch each level (think naive Fibonacci):

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

The call tree doubles at each level. Total calls grow exponentially — roughly O(2^n). In interviews, name this immediately and offer memoization or bottom-up DP to bring it to O(n).

**Divide and conquer — often O(n log n).** Merge sort splits in half (log n levels) and does O(n) merge work per level → O(n log n). Same pattern appears in fast FFT-style problems and some tree algorithms.

Complexity cheat sheet for interviews

Memorize the ordering. When comparing approaches, refer to where each sits on this ladder:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2^n) < O(n!)

O(1) — constant

Hash map lookup, array index access, pushing to a stack. Does not grow with input size.

O(log n) — logarithmic

Binary search, balanced BST operations, repeatedly halving the search space. If you eliminate half the remaining data each step, think log n.

O(n) — linear

Single scan, two pointers on a sorted array, BFS/DFS when each node is visited once. Often the best you can do if you must examine every element.

O(n log n) — linearithmic

Efficient sorting, merge sort, heap operations over n items, divide-and-conquer with linear combine step. If your solution sorts the full input, start here.

O(n²) — quadratic

Nested loops, brute-force pair checking, simple DP on small grids. Common in naive solutions — interviewers often ask how you'd improve it.

O(2^n) and O(n!) — exponential / factorial

Generating all subsets or all permutations. Fine for n ≤ 20 in backtracking problems; unusable at scale. Name the pattern when you see bitmask or "try every ordering" approaches.

What interviewers want to hear

  1. **State Big O for time and space** after you describe the approach — not after you finish coding.
  2. **Tie complexity to a line of code** — "The nested loop over pairs gives O(n²)."
  3. **Compare to alternatives** — "Sorting first is O(n log n); a hash map lookup is O(n) average."
  4. **Call out trade-offs** — O(n) extra space for O(n) time is a deliberate exchange.

You do not need formal proofs. You need a consistent method: find the hot loop, count how many times it runs, express it in terms of n, drop constants, keep the dominant term.

When your solution might be too slow

Typical online judges and interview platforms handle roughly:

  • O(n) or O(n log n) — safe for n up to 10⁶ or more
  • O(n²) — fine for n ≈ 10³–10⁴
  • O(2^n) — only when n ≤ 20–25

If your brute force is O(n²) and constraints say n = 10⁵, stop and rethink before coding. That constraint is a hint.

Practice on real problems

Work through the study guide on LRU Cache — every operation is O(1) and you should explain why. Then compare with Merge Intervals from Data Stream, where the heap gives O(log n) per insertion.