Big-O: The Cost Of Code

An interviewer doesn’t end a coding round with “does it work?” — they end it with “what’s the complexity, and can you do better?” Every module after this one is built on that question, and every production outage caused by “it was fine in testing” is built on someone not asking it. This module makes you the person who reads a piece of code and instantly knows what it costs.

The Goal

• Explain what Big-O actually measures — and why O(2n) and O(n) are the same thing
• Name the six classes you’ll meet daily, with a Java example for each
• Derive the Big-O of any code you read: loops, nested loops, sequential blocks, recursion
• State space complexity separately from time, and know when it matters
• Recall the cost of every common Java collection operation without looking it up
• Say the interview script for stating complexity, smoothly, every single time

The Lesson

What Big-O actually measures

Big-O is not speed. It’s not seconds, not milliseconds, not “how fast is your laptop.” It answers one question:

When the input gets bigger, how much more work does this code do?

That’s growth. A function that does 3n + 50 operations and one that does n operations are both O(n) — because when n goes from 1,000 to 1,000,000, both grow the same shape: linearly. The 3 and the 50 stop mattering at scale, so Big-O drops them. Constants are about your hardware; growth is about your algorithm. Interviewers, and production systems, care about the second one.

Here’s why the shape is everything. Watch what happens to each class as n grows:

Read that O(n²) column again. At n = 1,000 it’s a million operations — fine. At n = 1,000,000 it’s a trillion — minutes of CPU time for one request. The code didn’t change. The input did. That’s the entire reason Big-O exists.

The six classes, one Java example each

O(1) — constant. Same cost no matter how big the input. Array index and HashMap.get are the classics:

int x = arr[500_000];          // jumping to an index is one memory hop
String name = map.get(42);     // hash the key, jump to the bucket - one hop

O(log n) — logarithmic. Each step kills half of what’s left. Binary search on a sorted array:

int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] == target) break;
    if (arr[mid] < target) lo = mid + 1;   // throw away the left half
    else hi = mid - 1;                     // throw away the right half
}

A billion elements → ~30 steps. Halving is absurdly powerful; the binary search module is dedicated to it.

O(n) — linear. Touch every element once. The plain scan:

int max = Integer.MIN_VALUE;
for (int value : arr) {
    if (value > max) max = value;   // one look per element
}

O(n log n) — the sorting class. Every good general-purpose sort lives here. You’ll usually meet it as one line:

Arrays.sort(arr);   // dual-pivot quicksort for primitives - O of n log n

Rule of thumb: if your solution starts with “first, sort it,” you’ve already paid n log n.

O(n²) — quadratic. A loop inside a loop, both over the input. The brute-force pair check:

for (int i = 0; i < arr.length; i++) {
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[i] + arr[j] == target) { /* found a pair */ }
    }
}

Fine at n = 100. Dead at n = 100,000. Most of this DSA track is learning patterns that turn an O(n²) brute force into O(n) or O(n log n).

O(2^n) — exponential. Each call spawns more calls. Naive Fibonacci:

static long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);   // two branches per call - the tree doubles every level
}

fib(50) makes billions of calls. The fix (memoization) is a one-line change you’ll learn in the DP module — it drops 2^n to n.

How to READ code and derive its Big-O

This is the actual skill. Three rules cover almost everything you’ll see:

flowchart TD
    A["Read the code structure"] --> B["Nested loops over the input"]
    A --> C["Sequential blocks one after another"]
    A --> D["Recursion"]
    B --> E["MULTIPLY them - n times n is n squared"]
    C --> F["ADD them and keep the biggest - n plus n squared is n squared"]
    D --> G["branches to the power of depth"]

Rule 1 — nested loops multiply. A loop of n inside a loop of n is n × n = O(n²). A loop of n with a binary search inside is n × log n = O(n log n).

Rule 2 — sequential blocks add, then the biggest wins. One O(n) loop followed by another O(n) loop is n + n = 2n = O(n), not O(n²). Multiplication needs nesting. An O(n) scan followed by an O(n²) check is n + n² = O(n²) — the dominant term swallows the rest, the same way constants got dropped.

Rule 3 — recursion is branches^depth. Naive fib makes 2 calls per call (branches = 2) and goes n levels deep → O(2^n). Binary search makes 1 recursive call per call and goes log n deep → O(log n). When you see recursion, ask exactly two questions: how many calls does each call make? and how deep does it go?

Two traps inside these rules:

• The inner loop must depend on the input. for (int j = 0; j < 5; j++) inside an n-loop is 5n = O(n). A constant-size inner loop doesn’t multiply.
• Hidden loops count. list.contains(x) inside a loop looks like one line but it scans the whole list — that innocent line just made your loop O(n²). Library calls have costs; you have to know them (table below).

A full worked derivation — do this out loud, the way you would at a whiteboard:

static boolean hasPairWithSum(int[] arr, int target) {
    Arrays.sort(arr);                        // step A
    for (int i = 0; i < arr.length; i++) {   // step B - n iterations
        int need = target - arr[i];          //   O(1)
        if (binarySearch(arr, need) >= 0) {  //   O(log n) per iteration
            return true;
        }
    }
    return false;                            // A and B are sequential
}

Step A is a sort: O(n log n). Step B is a loop of n iterations, each doing O(log n) work — nested, so multiply: n × log n = O(n log n). A and B run one after the other — sequential, so add and keep the biggest: n log n + n log n = O(n log n) total. Three rules, one clean answer, said in fifteen seconds. (And the pattern instinct kicks in: on a sorted array, two pointers does this same job in O(n) — that’s module DSA 03.)

Best, average, worst — which one is Big-O quoting? By default, the worst case — that’s the promise that holds no matter what input arrives, and it’s what you state in interviews unless asked otherwise. The linear scan that finds its target at index 0 did O(1) work that time, but you don’t get to choose your inputs in production. The one place average-vs-worst genuinely matters in your daily toolkit: HashMap is O(1) average but O(n) worst case if every key lands in one bucket — say “average” when you quote it and you’ll sound like someone who actually knows the structure.

Space complexity — the second answer

Time is “how many operations.” Space is “how much extra memory, beyond the input itself.”

// O(1) space - a few variables, no matter how big arr is
int sum = 0;
for (int v : arr) sum += v;

// O(n) space - the set can grow to hold every element
Set<Integer> seen = new HashSet<>();
for (int v : arr) seen.add(v);

The classic trade you’ll make all through this track: spend O(n) space to buy O(n) time. Two Sum brute force is O(n²) time, O(1) space; the HashMap version is O(n) time, O(n) space. Neither is “better” — it’s a trade, and saying the trade out loud is what separates you in an interview. Recursion has space too: every call sits on the stack, so n-deep recursion is O(n) space even with zero variables.

Amortized cost, in one paragraph

ArrayList.add is listed as O(1), but sometimes the backing array is full — then it allocates a new array ~1.5× bigger and copies everything over, which is O(n) for that one call. So how is add “O(1)”? Because the expensive copy happens so rarely (only when capacity runs out, and each grow buys room for many future adds) that averaged over a long sequence of adds, the cost per add is constant. That’s amortized O(1): occasionally expensive, cheap on average, guaranteed by the math of the growth factor. When an interviewer asks “is ArrayList add really O(1)?” — this paragraph is the answer they want.

The interview script

When you finish coding, don’t wait to be asked. Say this, every time:

“Time complexity is O(n) — the single pass over the array dominates, and each HashMap operation inside it is O(1). Space is O(n) for the map in the worst case. The brute force would be O(n²) time but O(1) space, so I’m trading memory for speed here.”

Four beats: time + why, space + why, what the brute force was, what trade you made. Practicing this sentence shape until it’s automatic is worth as much as solving ten extra problems.

One more interview weapon: read the constraints to predict the expected complexity. A modern CPU does very roughly 100 million simple operations in a second, so the problem’s stated input size tells you which class the setter expects:

Before writing a line of code, glance at n and you already know roughly which pattern the problem wants. That’s pattern-first thinking starting from the constraints alone.

See It Move

Drag the slider and watch the operation counts — the gap between the bars IS this entire module.

Step through it and notice:

• At small n the bars look almost equal — this is exactly why slow code passes testing and dies in production.
• O(log n) barely moves even when n explodes; that flatness is the superpower behind binary search and database indexes.
• O(n) vs O(n log n) stay close for a long time — that’s why “just sort it first” is usually an acceptable price.
• Find the n where O(2^n) leaves the chart entirely. It’s embarrassingly small.

Spot The Pattern

The recognition skill here: look at code, name its cost. These are the structural tells:

Where It Runs In Real Life

The endpoint that melts at 10k users. A startup ships an API that, for each user in a list, loops the list again to find duplicates — O(n²). At 200 beta users that’s 40,000 checks, invisible. At 10,000 users it’s 100 million checks per request; response time goes from 20ms to 30+ seconds, requests pile up, the server runs out of threads, and the whole service is down. Nobody wrote a “bug” — someone just never asked the growth question. This exact story is behind a huge share of real production incidents.

Database full scan vs index. WHERE email = ? on an unindexed column makes the database read every row — O(n), and at 50 million rows that’s seconds per query. Adding an index puts the column in a B-tree, turning the lookup into O(log n) — a handful of page reads, sub-millisecond. When you later learn “always index your WHERE columns,” this module is the reason why.

Your daily Java collections. Every collection choice is a Big-O choice. Burn this table in — it’s the most-asked Java interview table in existence:

The one-line summary: need order → TreeMap and pay log n; need raw speed by key → HashMap; need a growable sequence → ArrayList, but never contains on it in a loop. (Full tour in the Collections module.)

Payment batch jobs. A nightly job reconciling transactions against a bank statement: the O(n²) version (for each txn, scan the statement) is fine at launch and takes 14 hours two years later when volume is 100×. The O(n) version (load the statement into a HashMap, then one pass) still finishes in minutes. Same job, same hardware — different growth curve.

Build This

You’re going to measure the table above instead of trusting it. One program, 1 million elements, three operations timed with System.nanoTime.

1. Create BigOBench.java and type this (no copy-paste — typing it is the rep):

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class BigOBench {

    public static void main(String[] args) {
        int n = 1_000_000;
        int[] arr = new int[n];
        Random rng = new Random(42);
        for (int i = 0; i < n; i++) arr[i] = rng.nextInt();

        int target = arr[n - 7];   // a value we know exists, near the end

        // --- O(n): linear scan ---
        long t1 = System.nanoTime();
        boolean foundScan = false;
        for (int v : arr) {
            if (v == target) { foundScan = true; break; }
        }
        long scanNanos = System.nanoTime() - t1;

        // --- O(n) build once, then O(1) lookup: HashMap ---
        Map<Integer, Boolean> map = new HashMap<>();
        for (int v : arr) map.put(v, true);

        long t2 = System.nanoTime();
        boolean foundMap = map.containsKey(target);
        long mapNanos = System.nanoTime() - t2;

        // --- O(n log n): sort ---
        int[] copy = Arrays.copyOf(arr, n);
        long t3 = System.nanoTime();
        Arrays.sort(copy);
        long sortNanos = System.nanoTime() - t3;

        System.out.println("n = " + n);
        System.out.printf("%-22s %15s%n", "Operation", "Time");
        System.out.printf("%-22s %12d us%n", "Linear scan O(n)", scanNanos / 1_000);
        System.out.printf("%-22s %12d us%n", "HashMap lookup O(1)", mapNanos / 1_000);
        System.out.printf("%-22s %12d us%n", "Sort O(n log n)", sortNanos / 1_000);
        System.out.println(foundScan && foundMap ? "(both lookups found the target)" : "(BUG: lookup disagreed)");
    }
}

2. Compile and run:

javac BigOBench.java
java BigOBench

3. Read your table. The HashMap lookup should be thousands of times faster than the scan — that’s O(1) vs O(n) made physical. The sort sits in between, exactly where n log n belongs.

4. Break it: change target to 12345 (a value almost certainly not in the array). The scan now can’t break early and pays the full n every time. Re-run — the scan gets slower, the map doesn’t care. You just observed worst case vs best case.

5. Extend it: wrap the whole timing block in a loop over n = 1_000, 10_000, 100_000, 1_000_000 and print one row per n. Watch the scan column grow ~10× per step while the map column stays flat. You’ve just drawn the BigOExplorer chart with your own CPU.

6. Extend it again: add an O(n²) contender — count duplicate pairs with two nested loops — but only run it for n up to 50,000. Try 1,000,000 if you dare, then Ctrl+C and appreciate why this module exists.

Problems To Solve

Big-O isn’t a problem category — it’s the lens. So the drill is: solve each of these, then state time and space using the interview script before checking any solution.

The rule: solve until you can write the template from memory; if stuck 25 min, read the approach, close it, re-solve from scratch.

Check Yourself

1. Big-O measures growth, not speed. What does that distinction mean, in one sentence?
2. Why is an algorithm doing 5n + 200 operations still O(n)?
3. Two loops over the same array, one after the other: what’s the complexity, and why isn’t it O(n²)?
4. list.contains(x) inside a for-loop over the list — what’s the real complexity, and what one-word change fixes it?
5. Naive recursive Fibonacci is O(2^n). Derive that from the branches-and-depth rule.
6. ArrayList.add sometimes costs O(n). Why do we still call it O(1)?
7. HashMap get vs TreeMap get — costs of each, and what is TreeMap’s log n buying you?
8. You finish coding in an interview. Say the four-beat complexity script for a HashMap-based Two Sum.

Explain it out loud: Teach the empty chair why the same code can be fine at 1,000 users and down at 1,000,000 — using the n-growth table, the nested-vs-sequential loop rule, and the ArrayList-grow story — without saying the word “fast” even once. If you reach for “fast,” restart.

Still Unclear?

I'm learning Big-O. Show me 5 short Java methods one at a time (loops, nested
loops, sequential loops, a hidden contains call, simple recursion) and make ME
derive the time and space complexity of each before you reveal it. Correct my
reasoning, not just my answer.

Explain amortized O(1) for ArrayList.add using a bank-balance analogy: every
cheap add deposits a little time-credit, and the rare O(n) grow spends it.
Then quiz me: why does growing by 1.5x give amortized O(1) but growing by
adding 10 slots each time does NOT?

I claimed two sequential O(n) loops are O(n^2) and got corrected. Walk me
through why nesting multiplies but sequence adds, with a concrete operation
count at n = 1000 for both shapes, then give me 3 tricky loop structures to
classify myself.

Why AI Can’t Do This For You

AI will happily tell you the complexity of any code you paste. But in the interview there’s no paste — there’s you, a marker, and “can you do better?” Recognizing that your own solution hides an O(n) contains inside a loop, in the moment, under pressure, is a reading skill that only lives in your head or doesn’t.

And in the job, the O(n²) endpoint never announces itself — it ships green, passes review, and melts eight months later at 3 a.m. when traffic grows. The engineer who asks “what happens to this loop at 100× the data?” before shipping is the one who never gets that call. No prompt asks that question for you; the habit has to be yours.

Module done? Add it to today’s tracker