How do you work out the time complexity of a method, and why does O(n²) matter when the code looks fine?

The Answer

• Big-O describes how the work grows as the input grows, not how fast the code is. It drops constants and lower-order terms on purpose — they depend on the machine, and the growth does not.
• Read it off the structure:
  • one loop over n → O(n);
  • two loops one after the other → still O(n), because you add;
  • a loop inside a loop over the same input → O(n²), because you multiply;
  • the range halving each step → O(log n).
• The cost you miss is inside the method calls. list.contains(x) is a scan. string += x copies the whole string. Put either in a loop and you have written O(n²) that reads like O(n).
• "Fine on my machine" usually means the test input was small. O(n²) and O(n) are indistinguishable at n = 100 and four hours apart at n = 1,000,000.
• Say the worst case unless you state otherwise, and say what n is.

Understand It

Count the work, do not time it

Timing a JVM tells you about JIT warm-up, garbage collection and what else the laptop was doing. Counting steps tells you about the algorithm. Everything on this page counts.

for each item in list:          # runs n times
    doSomething(item)           # cost of the body, call it c
                                # total: c · n  →  O(n)

for i in 0..n:                  # n times
    for j in 0..n:              # n times, for EACH i
        doSomething(i, j)       # total: n · n  →  O(n²)

while lo <= hi:                 # range halves each pass
    mid ← middle of lo..hi      # n → n/2 → n/4 → ... → 1
                                # that is log₂(n) passes  →  O(log n)

The rule that does the most work: nested loops over the same input multiply; sequential loops add. Two passes over a million rows is two million steps. One pass containing another pass is a trillion.

The scan hiding inside contains

List.contains reads like a question. It is a loop:

for (int n : new int[] {1000, 4000, 16000}) {
    List<Integer> list = listOf(n);
    long steps = 0;
    for (int i = 0; i < 200; i++) steps += scanSteps(list, n - 1);
    System.out.printf("n=%-6d 200 lookups cost %d steps%n", n, steps);
}

n=1000   200 lookups cost 200000 steps
n=4000   200 lookups cost 800000 steps
n=16000  200 lookups cost 3200000 steps

Four times the data, four times the work, for the same number of lookups. That is O(n) per lookup, and it is exactly what you do not want inside a loop — because then the number of lookups grows with n too, and the total is O(n²).

This is the single most common accidental quadratic in Java:

// O(n * m) — a scan of `seen` for every candidate
for (String candidate : candidates)
    if (seen.contains(candidate)) ...      // seen is a List

// O(n) — a hash lookup for every candidate
Set<String> index = new HashSet<>(seen);
for (String candidate : candidates)
    if (index.contains(candidate)) ...

One line — building the HashSet — changes the growth rate. Nothing about the loop changed.

The copy hiding inside +=

String is immutable, so s = s + "x" cannot extend anything. It allocates a new string and copies every character already there:

for (int n : new int[] {1000, 2000, 4000}) {
    System.out.printf("n=%-6d chars copied by += : %d%n", n, concatCopies(n));
}

n=1000   chars copied by += : 499500
n=2000   chars copied by += : 1999000
n=4000   chars copied by += : 7998000

Double the loop count and the copying quadruples — 0.5M, 2M, 8M. That is the signature of O(n²) in a loop whose body is one short line. StringBuilder appends into a buffer it owns, making the same loop O(n).

Amortised is not the same as average

ArrayList.add is documented as amortised O(1), and the word matters. Most appends are a single array write. Occasionally the array is full and every element is copied to a bigger one:

for (int n : new int[] {1000, 2000, 4000}) {
    long[] g = growth(n);
    System.out.printf("n=%-6d regrowths: %2d, elements copied: %d%n", n, g[0], g[1]);
}

n=1000   regrowths: 12, elements copied: 2456
n=2000   regrowths: 14, elements copied: 5541
n=4000   regrowths: 15, elements copied: 8317

Doubling n adds about two regrowths, not twice as many — growth is multiplicative, so the count is logarithmic. And the total copying stays proportional to n: around 2× the elements appended, so each append costs O(1) on average across the sequence, which is what amortised means.

Amortised says nothing about a single call. One unlucky add copies four million elements. That is invisible in a throughput benchmark and very visible in a latency percentile.

Reference

The costs worth knowing by heart, because they are the ones that appear inside loops:

Reading a method top to bottom:

static int countPairs(List<Integer> values, int target) {   // n = values.size()
    int count = 0;
    for (int i = 0; i < values.size(); i++) {               // n iterations
        for (int j = i + 1; j < values.size(); j++) {       // ~n/2 on average
            if (values.get(i) + values.get(j) == target)    // O(1) each
                count++;
        }
    }
    return count;                                            // n · n/2 → O(n²)
}

n/2 is dropped because constants are dropped. The same problem in one pass, trading memory for time:

static int countPairs(List<Integer> values, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    int count = 0;
    for (int v : values) {                                   // n iterations
        count += seen.getOrDefault(target - v, 0);           // O(1) average
        seen.merge(v, 1, Integer::sum);                      // O(1) average
    }
    return count;                                            // O(n) time, O(n) space
}

Space complexity is counted the same way, and is the thing the first version was quietly winning on: O(1) extra memory against O(n).

Scenarios

A report that got slow after a good quarter. The code joins two lists with a nested loop. At 200 customers it is 40,000 comparisons and nobody notices; at 20,000 customers it is 400 million. Nothing changed but the data. This is the normal way quadratic code is discovered — by growth, in production.

The profiler blames String.concat. It is not the concatenation that is slow, it is that there are n of them each copying n/2 characters. Replacing the loop body changes nothing; replacing the accumulator with a StringBuilder changes the growth rate.

A "cache" that is a List. Someone adds if (!cache.contains(key)) in front of an expensive call. Each check is a scan, so the cache costs more as it gets more useful. A HashSet has the same API shape and O(1) lookups.

When O(n²) is the right answer. For n under a few hundred, the simple quadratic loop is often faster than the clever linear one — no hashing, no allocation, cache-friendly. Big-O is about growth, and if n cannot grow, it is not the thing to optimise. Say so explicitly rather than pretending not to know.

Interviewer's Next Move

1. "Two sequential loops over the same list — O(n) or O(n²)?" O(n). Sequential work adds: n + n = 2n, and the constant drops. Only nesting multiplies. The question is really testing whether you read structure or count for keywords.

2. "Why is HashMap.get O(1) if it has to handle collisions?" It is O(1) on average, assuming a decent hash spreading keys across bins. In the worst case every key lands in one bin — then it is O(n) for a list-shaped bin, or O(log n) since Java 8 treeifies long bins. A deliberately bad hashCode makes this the worst case on purpose, which is the HashDoS attack.

3. "What does amortised O(1) mean for a latency SLA?" That the average over many calls is constant, not that any single call is. One add in log n copies the whole array, so it shows up in p99.9 rather than the mean. If the tail matters, size the list up front or pick a structure that does not reallocate.

4. "Your solution is O(n) time and O(n) space; the other is O(n²) and O(1). Which do you ship?" Depends on n and on where it runs. A million rows makes the quadratic one impossible. A fixed twenty rows in a memory-constrained device makes the extra map wasteful. The answer an interviewer wants is that you know it is a trade, and which quantity you traded.

5. "How do you find this in existing code?" Look for a method call inside a loop whose cost depends on collection size — contains, indexOf, remove(Object), get(i) on a LinkedList, string concatenation. Then confirm with a measurement at two input sizes: if quadrupling the input roughly sixteen-times the work, it is quadratic.

Check Yourself

A loop appends to a String 10,000 times and it is slow. Where is the quadratic, given the loop body is one line? In +=. Each concatenation allocates a new String and copies everything accumulated so far, so the total copying is 0 + 1 + ... + n-1, which grows with n². StringBuilder makes it O(n).

ArrayList.add is amortised O(1). What is the worst single call? O(n) — the one that finds the array full and copies every element into a larger one. It happens about log₁.₅(n) times across n appends, which is why the average stays constant.

How do you tell O(n) from O(n²) with a stopwatch and no profiler? Run it at n and at 4n. Linear work takes about four times as long; quadratic takes about sixteen. Two points and a ratio are enough to distinguish them, which is why counting at two sizes beats timing at one.