Stating "this is O(n)" is easy. Explaining why it is O(n), walking the interviewer through your reasoning, and catching subtle traps that change the answer from O(n) to O(n^2), that is what separates candidates who pass from candidates who get a "no hire" with the note "weak on fundamentals."

Interviewers do not just want the final answer. They want to see your thought process. Can you look at a piece of code and reason about how its running time grows? Can you spot a hidden quadratic buried inside an innocent-looking loop? Can you handle multiple variables, logarithmic factors, and amortized costs without hand-waving?

This chapter gives you a repeatable system for analyzing and explaining complexity so you never freeze when the interviewer asks, "What is the time complexity of your solution?"

Many candidates treat complexity as a lookup table: single loop is O(n), nested loop is O(n^2), binary search is O(log n). That works for toy examples. It falls apart the moment code does something slightly different, like a nested loop where the inner loop runs a decreasing number of times, or a loop that calls a library method with its own hidden cost.

The real skill is analysis, not memorization. You need to count the total work done across all iterations, account for hidden operations, and express the result in terms of the input variables.

Every time you need to analyze complexity, follow these four steps:

Let us apply this framework to five common code patterns.

Analysis: One loop, runs n times, each iteration does O(1) work (array access and addition). Total: O(n).

This is the simplest case, and most candidates get it right. But here is how you should explain it in an interview:

Short, clear, and it shows you understand why, not just what.

Not all nested loops are O(n^2). The total work depends on how many times the inner loop runs across all iterations of the outer loop. Consider these two examples:

Example A: Classic O(n^2)

The inner loop runs n times for each of the n outer iterations. Total: n * n = O(n^2).

Example B: Triangular Loop, Still O(n^2)

Many candidates pause here. The inner loop runs (n - i) times. The total work across all iterations is:

(n) + (n-1) + (n-2) + ... + 1 = n(n+1)/2

That is still O(n^2). The constant factor (1/2) drops out. Here is the key insight to communicate: "Even though the inner loop shrinks each time, the sum of 1 through n is n-squared over 2, which is O(n^2)."

**Example C: Independent Variables, O(n * m)**

When the outer loop runs n times and the inner loop runs m times, you cannot say O(n^2) unless n equals m. The correct answer is O(n * m). Always identify whether nested loops use the same variable or different ones.

That last row surprises people. Let us look at it next.

The inner loop increments by i each time, so it runs n/i iterations. The total work is:

n/1 + n/2 + n/3 + ... + n/n = n * (1 + 1/2 + 1/3 + ... + 1/n)

The sum 1 + 1/2 + 1/3 + ... + 1/n is the harmonic series, which grows as O(log n). So the total is O(n log n).

This pattern appears in the Sieve of Eratosthenes, divisor enumeration, and several string/array problems. If you spot an inner loop that divides the range by the outer variable, think harmonic series.

Recursive algorithms need a different analysis approach. The key tool is the recursion tree: draw out the calls, figure out how much work each level does, and sum across all levels.

Example: Merge Sort

At each level of recursion, the total work across all calls is O(n) because we split the array into halves and merge takes linear time per level. The tree has log n levels (we keep halving). Total: O(n log n).

Example: Fibonacci (Naive)

Each call branches into two calls. The tree has depth n. The number of nodes roughly doubles at each level, giving us O(2^n) total calls. Each call does O(1) work, so the total is O(2^n).

Here is a common interview mistake: saying Fibonacci is O(n^2) because "there are two calls and the input is n." The branching factor matters enormously. Two branches at every level means exponential, not polynomial.

The tree grows exponentially. Every additional level roughly doubles the nodes.

Some operations are expensive occasionally but cheap most of the time. Amortized analysis spreads the cost over a sequence of operations.

Example: ArrayList / Dynamic Array

When the internal array is full, ArrayList doubles its capacity and copies all elements, which costs O(n). But this happens only after n insertions. If we spread that O(n) cost across the n insertions that preceded it, each insertion costs O(1) amortized.

Here is how to explain this in an interview:

This reasoning also applies to operations on hash maps (rehashing), StringBuilder (capacity doubling), and Union-Find with path compression.

These are the mistakes that cost candidates offers. You write what looks like an O(n) solution, but a hidden operation makes it O(n^2).

Trap 1: String Concatenation in Java

Java strings are immutable. Each += creates a new string and copies all previous characters. The work is 1 + 2 + 3 + ... + n = O(n^2). Use StringBuilder instead, which gives you O(n) total.

Trap 2: List Operations Inside Loops

ArrayList.remove(0) shifts all remaining elements left, which is O(n). Inside a loop of n iterations, that gives O(n^2). Use LinkedList or Deque if you need frequent removal from the front.

Trap 3: Sorting Inside a Loop

If you sort inside a loop, the total cost includes the sort as a factor. O(n) iterations times O(n log n) sort gives O(n^2 log n). Ask yourself: can you sort once outside the loop?

Trap 4: Substring in Older Java

In Java 7+, String.substring() creates a new string and copies characters, making it O(k) where k is the substring length. If you call substring inside a loop, those costs add up.

When your input has two different dimensions, you must express complexity in terms of both. A common interview question: "Given two sorted arrays of size n and m, merge them."

This is O(n + m), not O(n * m). Each element is visited at most once, and the pointers only move forward. The total work is proportional to the sum of the two sizes.

Contrast this with: "For each element in array A, check if it exists in array B using a linear scan." That is O(n * m) because for each of n elements, you scan up to m elements.

O(log n) shows up in three main places:

When you see a log factor, identify which of these three sources it comes from. That makes your explanation concrete and convincing.

Interviewers notice hesitation. Here is a template for explaining complexity clearly:

If the interviewer pushes back or asks a clarifying question, that is a good sign. It means they are engaged. Walk them through the specific part they are questioning, ideally by counting iterations on a small example.

Q1: You have a loop that iterates n times, and inside it you call `Arrays.sort()` on an array of size k. What is the total time complexity?

The sort is O(k log k) per call. Called n times, the total is O(n * k log k). If k is constant (does not grow with input), this simplifies to O(n). If k equals n, it becomes O(n^2 log n). Always ask: does the inner operation depend on n?

Q2: Explain why building a hash map from n elements is O(n), but looking up n elements in a balanced BST is O(n log n).

Hash map insertion is O(1) amortized (assuming good hash function, rare collisions). Doing it n times gives O(n). BST lookup is O(log n) per query because you traverse a path from root to leaf in a balanced tree of height log n. Doing it n times gives O(n log n). The data structure's per-operation cost directly determines the total.

Q3: A candidate says their solution is O(n) but their code concatenates strings with `+=` inside a loop. What is the actual complexity?

O(n^2). Each concatenation copies the entire string built so far. The total characters copied are 1 + 2 + 3 + ... + n = n(n+1)/2 = O(n^2). The fix is to use StringBuilder, which appends in O(1) amortized time.

Q4: What is the time complexity of BFS on a graph with V vertices and E edges?

O(V + E). BFS visits each vertex once (O(V)) and examines each edge once (O(E)). The total is their sum, not their product, because we iterate over adjacency lists, not a full V x V matrix.

In the next chapter, we will use this analysis skill in a very practical way: discussing space-time trade-offs with your interviewer, which is one of the most common follow-up questions after you present a solution.