Big-O and Time Complexity: Reading an Algorithm’s Cost Straight Off the Code

Two photo apps do the exact same thing — scroll a wall of thumbnails. On your phone, with a few hundred pictures, both feel instant. Hand the same two apps to someone with sixty thousand photos and they split in two: one still snaps open, the other chews on a spinner for ten seconds. Same feature, same phone, same task. The only thing that changed is how each one grows as the pile gets bigger.

That difference has a name, and it’s the single most useful idea for reasoning about code before you ever run it: Big-O notation, the language of time complexity. It doesn’t measure seconds — it measures shape: how the work grows as the input grows. By the end of this article you and I will be able to glance at a chunk of code and read its Big-O straight off the page, and you’ll understand the one accounting trick — amortized analysis — that almost everyone quietly confuses with something else.

Let’s start nowhere near a computer

It’s the end of a dinner and the sink is full. Someone asks, "how long will the dishes take?"

The useless answer is "twelve minutes." It’s useless because it depends on everything except the actual problem — how fast you scrub, whether the tap runs hot, whether you stop to chat. Run the same pile tomorrow after a coffee and you’ll get a different number. Seconds are about you and your kitchen, not about the task.

The useful answer describes how the chore scales. "Twice the dishes, twice the time" tells your friend something true no matter whose hands are in the sink. And notice you didn’t sweat whether each plate takes eight seconds or ten — that detail changes the total but not the shape. Eight-per-plate and ten-per-plate both say "the work grows in step with the pile." That’s the first instinct of Big-O: describe the shape of the growth, and stop caring about the constant per-item cost.

Here’s the second instinct, hiding in the same sink. Before you touch a plate you wipe the counter — a flat two minutes, whether there are three dishes or three hundred. With three dishes that wipe is the whole job. With three hundred, nobody would ever mention it. So a fixed setup cost that looked huge on a tiny pile simply vanishes once the pile is big. Big-O keeps only the part that grows and throws away the fixed overhead, because at scale the overhead is a rounding error.

And the pile can grow in genuinely different shapes depending on what you do with it:

• Grab the top plate. One motion, whether the stack is 5 high or 5,000. The pile’s size doesn’t enter into it at all.
• Wash every plate once. Do the pile, and the time tracks the count — double the dishes, double the work.
• Sort the plates biggest-to-smallest by holding up every plate against every other one. Now each plate drags you past all the rest, and the effort balloons far faster than the pile itself.

Those three chores are three different growth shapes — flat, proportional, and explosive — and every bit of this article is just about naming them precisely and spotting which one your code is doing.

Where you already meet it

Once you think in shapes, the split from the photo apps is everywhere:

• "It worked in testing, then fell over in production." The classic story of code that’s fine at 100 rows and unusable at 10 million — a growth shape nobody checked until the pile got real.
• Your database’s query plan. Add the right index and a lookup uses a sorted structure it can halve — fast even on a billion rows. Miss the index and it scans every row. EXPLAIN is literally the database telling you its Big-O.
• A progress bar that crawls near the end, or a search box that lags only when the list gets long — the felt symptom of the wrong growth shape.
• Compression, encryption, a game’s physics loop — every "why is this slow only on big inputs?" is a time-complexity question wearing work clothes.

The reason to learn this on paper instead of with a stopwatch is simple: a benchmark tells you the app is slow today, on this input, on this laptop. Big-O tells you it will always get slow, and exactly how fast the trouble arrives as the input grows. One is a symptom; the other is the diagnosis.

What it actually looks like

Before any code, here’s the whole zoo on one chart. The horizontal axis is the input size n; the vertical axis is the number of operations. Every curve is a growth shape, and the gaps between them are the entire reason this topic matters.

Read it from the floor up. O(1) never lifts off — the flat line is the "grab the top plate" chore. O(log n) rises so gently it’s almost flat; O(n) is the honest straight diagonal; O(n²) curls upward and then bolts; and O(2ⁿ) barely registers at first and then leaves the top of the chart entirely. The lesson isn’t any single curve — it’s that a change in shape dwarfs any change in speed. A slow computer running O(log n) will smoke a supercomputer running O(2ⁿ) the moment n gets interesting.

Put numbers on it. Here’s what each shape costs when the pile has a thousand items versus a million:

Stare at the O(n²) row. Going from a thousand items to a million — a 1,000× bigger pile — costs a million times more work, not a thousand times. That superlinear penalty is why an O(n²) solution that flies through your test data can wedge a production server solid.

The exponential and factorial shapes don’t even belong in a "big n" table — they die far earlier. 2ⁿ is already over a quadrillion by n = 50, and n! blows past that by n = 20. If your algorithm is O(2ⁿ) or O(n!), the only inputs it survives are the ones in the low tens. That’s not a footnote; it’s the whole reason we hunt for polynomial-time algorithms.

Let’s read it straight off the code, step by step

Here’s the promise of this whole section: you shouldn’t have to run code to know its Big-O. A handful of reading rules — count the loops, watch what halves, follow the recursion — let you derive it by eye. We’ll build those rules one at a time, on tiny methods whose cost we can actually count.

Step 1 — count operations, not seconds

The unit of Big-O is the operation, not the second. An operation is any fixed-cost step: an addition, a comparison, an array index, a pointer follow. We count how many of those the code does as a function of n, and we don’t care that a multiply is a hair slower than an addition — those are exactly the constants we drop.

/** O(1): one indexed read, no matter how large the array. */
public static int first(int[] a) {
    return a[0];
}
 
/** O(n): touch every element once. */
public static long sum(int[] a) {
    long total = 0;
    for (int x : a) {   // runs n times
        total += x;
    }
    return total;
}

first does the same one operation whether the array holds ten values or ten billion — the size never enters the count, so it’s O(1). sum runs its loop body once per element: n additions, so n operations, so O(n). The rule: a single loop over n things is O(n); work that ignores the size is O(1). We measure the count, never the clock — because the clock changes with the machine and the count doesn’t.

Step 2 — drop the constants and the lower-order terms

Real methods do several things. Suppose one wipes the counter (a fixed 90 operations of setup), then runs a nested pass costing 3n², then a single pass costing 5n. Its exact operation count is 3n² + 5n + 90. Big-O throws almost all of that away and calls it O(n²). Two moves are happening, and they’re worth separating.

Drop the constant multipliers. The 3 in 3n² depends on how many operations one loop iteration happens to cost — and that’s exactly the eight-versus-ten-seconds-per-plate detail we already agreed doesn’t change the shape. 3n² and n² both grow as "square of the input," so we keep n².

Drop the lower-order terms. Look at the diagram: at n = 5 the constant 90 is actually the biggest chunk of the bar — smaller inputs genuinely can’t tell these terms apart. But at n = 1,000 the 3n² term is 3,000,000 while 5n is 5,000 and the 90 is invisible. The fastest-growing term doesn’t just win; it wins by so much that everything else is noise. So 3n² + 5n + 90 becomes O(n²), full stop.

Step 3 — sequential loops add, nested loops multiply

Now the two rules that carry most of the work. When you have more than one loop, the question is whether they sit beside each other or inside each other.

Here’s the trap first. A beginner sees two loops and blurts "two loops, so it’s O(n²)." Watch why that’s wrong:

/** O(n): two loops one after another still ADD — 2n, not n². */
public static long sumPlusMax(int[] a) {
    long total = 0;
    for (int x : a) {          // n operations
        total += x;
    }
    int max = a[0];
    for (int x : a) {          // + n operations  → 2n
        max = Math.max(max, x);
    }
    return total + max;
}

Two loops, yes — but one after the other. The first does n steps and finishes; then the second does n steps. That’s n + n = 2n, and after we drop the constant, O(n). Sequential work adds. Ten passes over the array in a row would be 10n — still O(n), because a constant number of full passes is just a bigger constant.

Now put one loop inside the other and everything changes:

/** O(n²): the nested loop compares every unordered pair. Returns that count. */
public static long pairComparisons(int n) {
    long comparisons = 0;
    for (int i = 0; i < n; i++) {        // runs n times…
        for (int j = i + 1; j < n; j++) { // …and for each i, up to n times
            comparisons++;
        }
    }
    return comparisons;                   // n·(n−1)/2
}

The inner loop runs for every turn of the outer loop, so the counts multiply: roughly n × n = n². Nested work multiplies. The method returns the exact count, n·(n−1)/2, which for n = 1,000 is 499,500 — half a million operations to do something with a mere thousand items. That’s the quadratic penalty made concrete, and it’s why "compare every pair" (checking for duplicates the naive way, bubble sort, a nested scan) is the most common accidental O(n²) in real code.

The reading rule in one breath: loops side by side add their costs; a loop nested in a loop multiplies them. Three levels deep over the same n is O(n³). A loop of n wrapped around a loop of m is O(n·m). That’s most of Big-O reading right there.

Step 4 — halving is a logarithm

Some code doesn’t touch every element — it throws half of them away each step. That single move is the signature of O(log n).

/** O(log n): how many times n can be halved before reaching 1. */
public static int halvings(int n) {
    int steps = 0;
    while (n > 1) {
        n /= 2;        // discard half each step
        steps++;
    }
    return steps;      // ⌊log₂ n⌋
}

Count the loop iterations: n becomes n/2, then n/4, then n/8… until it hits 1. The number of times you can halve n before reaching 1 is, by definition, log₂ n. For n = 1,000 that’s just 9 steps; for a million, 19; for a billion, 30. The logarithm’s magic is that a thousand-fold bigger input costs only ten more steps.

The rule: whenever the input shrinks by a constant factor each step (halving, thirding, doubling toward a target), the count is O(log n). This is the beating heart of binary search and every balanced-tree lookup — halve the search space, and a billion possibilities fall in thirty questions. Contrast it with Step 1: a loop that shrinks the input by a constant amount (one element per step) is O(n); a loop that shrinks it by a constant factor is O(log n). Minus one versus divide by two — that’s the whole difference between linear and logarithmic.

Step 5 — recursion is branching to the power of depth

Loops are easy to count because they’re flat. Recursion fans out into a tree, and to read its cost you count the nodes of that tree. Here’s the notorious one:

/** O(2ⁿ): naive Fibonacci. calls[0] tallies every invocation. */
public static long fib(int n, long[] calls) {
    calls[0]++;
    if (n < 2) {
        return n;
    }
    return fib(n - 1, calls) + fib(n - 2, calls);
}

Each call spawns two more, which each spawn two more, all the way down. Draw it and the shape is unmistakable:

Two children per node, and the tree is about n levels deep, so the number of calls is roughly 2 to the power of the depth — O(2ⁿ). This isn’t hand-waving; the exact call count for fib(n) is 2·F(n+1) − 1, and it detonates: fib(10) makes 177 calls, but fib(30) makes 2,692,537. Same code, twenty more input, fifteen thousand times the work.

The reading rule for recursion: branching factor raised to the depth. Two recursive calls per level over n levels is 2ⁿ. One recursive call that halves the input (like binary search’s recursion) is a tree of depth log n with no branching — O(log n). A call that recurses on n − 1 a single time is a straight line of depth n — O(n).

Look again at the diagram and you’ll spot the waste: the yellow f(2) is computed from scratch more than once, and deeper trees repeat subproblems thousands of times. Remember the answer the first time and every repeat becomes a free lookup:

/** O(n): the same Fibonacci once each subproblem is remembered. */
public static long fibMemo(int n) {
    long[] memo = new long[n + 1];
    return fibMemo(n, memo, new boolean[n + 1]);
}
 
private static long fibMemo(int n, long[] memo, boolean[] done) {
    if (n < 2) {
        return n;
    }
    if (done[n]) {
        return memo[n];          // already solved — O(1) lookup
    }
    done[n] = true;
    return memo[n] = fibMemo(n - 1, memo, done) + fibMemo(n - 2, memo, done);
}

Now each of the n distinct subproblems is solved exactly once, so the whole thing is O(n). That collapse — from O(2ⁿ) to O(n) by refusing to redo work — is the entire idea behind dynamic programming, and it’s the single highest-leverage move in competitive coding. The complexity you read off the code told you precisely where the waste was.

Step 6 — best, average, and worst case

So far each method had one cost. But many do different amounts of work depending on which input arrives, and interviewers love to pin down which case you mean.

/** O(n): best case 1 compare, worst case n, average n/2 — all O(n). */
public static int linearSearch(int[] a, int target) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == target) {
            return i;
        }
    }
    return -1;
}

• Best case — the target is the very first element. One comparison, O(1). This is the luckiest input.
• Worst case — the target is last or absent. n comparisons, O(n). This is the input an adversary would hand you.
• Average case — over a random position, you scan about half the array, n/2 comparisons, which is still O(n) after dropping the constant.

When people say an algorithm "is O(n)" with no qualifier, they almost always mean the worst case — it’s the honest guarantee, the promise that holds no matter how mean the input. Best case is mostly trivia; average case matters when inputs really are random-ish. Say which one you mean, because for some algorithms they wildly diverge: quicksort is O(n log n) on average but O(n²) in its worst case, and that gap is the whole reason people care about the pivot choice.

Amortized isn’t average — the doubling-array argument

Here’s the one facet nearly everyone gets fuzzy on, and it’s worth slowing all the way down for. It lives inside something you use every day: the resizable array (ArrayList, and its cousins in every language). Appending to one is described as O(1) amortized — and understanding that phrase, and why it is not the same as "O(1) average," is what separates someone who memorized a table from someone who understands it.

Start with the mechanism. A dynamic array holds a fixed-size backing block. Most appends just drop a value into the next free slot — O(1). But when the block is full, the array allocates a bigger one and copies everything over — an O(n) operation for that one unlucky append. Here’s the honest version, counting every element it ever copies:

public static final class IntList {
    private int[] data = new int[1];
    private int size = 0;
    private long totalCopies = 0;
 
    public void add(int value) {
        if (size == data.length) {
            int[] bigger = new int[data.length * 2];   // double the capacity
            for (int i = 0; i < size; i++) {
                bigger[i] = data[i];                    // copy the old contents
                totalCopies++;
            }
            data = bigger;
        }
        data[size++] = value;
    }
    // size(), get(i), totalCopies() omitted
}

Now the bug that this section exists to kill. A tempting line of reasoning: "a single add can cost O(n) in the worst case; I do n of them in a loop; so the loop is O(n) × n = O(n²)." That multiplication looks airtight and it’s completely wrong — and it’s wrong in the exact way Step 3’s "two loops must be O(n²)" was wrong. You can’t just multiply the single-operation worst case by the number of operations, because the expensive appends can’t all happen. The fix is to stop charging per-operation and add up the whole sequence.

Watch when the copies actually happen. Starting from capacity 1, the array doubles at sizes 1, 2, 4, 8, …, so the expensive appends are rare and spaced ever further apart. Copy the total cost of n appends into one sum:

A geometric series is dominated by its last term, so all the copying across n appends adds up to less than 2n — I measured it, and 1,000 appends perform exactly 1,023 total copies. Spread that 2n of work across the n appends and each one carries an average of 2 operations. That’s O(1) per append — amortized. A single append can still spike to O(n), but you can never line up many spikes in a row: each doubling is "paid for" in advance by the cheap appends that had to fill the array to trigger it.

Now the distinction people botch. Amortized and average are both "roughly O(1) per operation," but they are different kinds of promise:

• Amortized O(1) is a guarantee over a sequence. Any n appends cost ≤ 2n total — worst case, adversary-proof, deterministic. There is no input, however malicious, that makes a run of appends cost more than O(n) total. The cost is smoothed across operations, not across luck.
• Average O(1) is a probabilistic expectation over inputs. A hash map’s lookup is O(1) on average assuming the keys scatter nicely. Feed it keys engineered to collide and every one lands in the same bucket, turning lookups into O(n). That’s not hypothetical — "hash flooding" is a real denial-of-service attack that weaponizes exactly this gap.

The one-line version: amortized is a promise about a sequence of operations; average is a bet about the distribution of inputs. An adversary can break your average case by choosing evil inputs; an adversary cannot break an amortized bound, because it holds for every possible sequence. Calling them synonyms — "amortized average O(1)" — is the tell that someone half-remembers the idea.

This "charge the sequence, not the operation" accounting is the aggregate method of amortized analysis, and once you’ve seen it here you’ll recognize it everywhere: it’s why the sliding window’s nested-looking shrink loop is really O(n), and it’s the same machinery Tarjan uses to prove union-find runs in near-constant time. A nested loop or a rare-but-expensive step is never automatically the product of its worst pieces — you have to add up the whole run.

Big-O reasoning vs. just timing it

The "obvious alternative" to analyzing complexity is to stop theorizing and run a stopwatch. Benchmarking is genuinely useful — but it answers a different question, and leaning on it alone is how scaling bugs slip through.

The trap is trusting the stopwatch alone. A benchmark on 100 rows can’t distinguish O(n) from O(n²) — both finish instantly — so the quadratic sails through review and detonates at 10 million rows in production. Big-O is the tool that sees that cliff coming from the code, before a single row of real data exists. And the reverse is just as true: Big-O can’t tell you whether the O(n) solution is actually faster than the O(n log n) one at your specific n = 500, because the constants it dropped might dominate at small sizes. The shape and the seconds are different questions; a good engineer reaches for both.

The complete implementation

Everything above, assembled — each method annotated with the Big-O you can now read off it, plus the memoized and amortized cases that prove complexity is a lever, not a fixed fact:

package dev.fiveyear.bigo;
 
public final class Complexity {
 
    private Complexity() {}
 
    /** O(1): one indexed read, no matter how large the array. */
    public static int first(int[] a) {
        return a[0];
    }
 
    /** O(n): touch every element once. */
    public static long sum(int[] a) {
        long total = 0;
        for (int x : a) {
            total += x;
        }
        return total;
    }
 
    /** O(n): two loops one after another still ADD — 2n, not n². */
    public static long sumPlusMax(int[] a) {
        long total = 0;
        for (int x : a) {          // n
            total += x;
        }
        int max = a[0];
        for (int x : a) {          // + n  → 2n = O(n)
            max = Math.max(max, x);
        }
        return total + max;
    }
 
    /** O(n²): the nested loop compares every unordered pair. Returns that count. */
    public static long pairComparisons(int n) {
        long comparisons = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                comparisons++;
            }
        }
        return comparisons;        // n·(n−1)/2
    }
 
    /** O(n²): true if any value repeats, by brute-force pair scanning. */
    public static boolean hasDuplicate(int[] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] == a[j]) {
                    return true;
                }
            }
        }
        return false;
    }
 
    /** O(log n): how many times n can be halved before reaching 1. */
    public static int halvings(int n) {
        int steps = 0;
        while (n > 1) {
            n /= 2;                // discard half each step
            steps++;
        }
        return steps;              // ⌊log₂ n⌋
    }
 
    /** O(n): best case 1 compare, worst case n, average n/2 — all O(n). */
    public static int linearSearch(int[] a, int target) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] == target) {
                return i;
            }
        }
        return -1;
    }
 
    /** O(2ⁿ): naive Fibonacci. calls[0] tallies every invocation. */
    public static long fib(int n, long[] calls) {
        calls[0]++;
        if (n < 2) {
            return n;
        }
        return fib(n - 1, calls) + fib(n - 2, calls);
    }
 
    /** O(n): the same Fibonacci once each subproblem is remembered. */
    public static long fibMemo(int n) {
        long[] memo = new long[n + 1];
        return fibMemo(n, memo, new boolean[n + 1]);
    }
 
    private static long fibMemo(int n, long[] memo, boolean[] done) {
        if (n < 2) {
            return n;
        }
        if (done[n]) {
            return memo[n];
        }
        done[n] = true;
        return memo[n] = fibMemo(n - 1, memo, done) + fibMemo(n - 2, memo, done);
    }
 
    /**
     * A grow-by-doubling int list. `totalCopies` exposes the amortized cost:
     * across any run of appends it stays below 2·size, so each append is
     * O(1) amortized even though a single append can copy the whole array.
     */
    public static final class IntList {
        private int[] data = new int[1];
        private int size = 0;
        private long totalCopies = 0;
 
        public void add(int value) {
            if (size == data.length) {
                int[] bigger = new int[data.length * 2];
                for (int i = 0; i < size; i++) {
                    bigger[i] = data[i];
                    totalCopies++;
                }
                data = bigger;
            }
            data[size++] = value;
        }
 
        public int get(int index) {
            return data[index];
        }
 
        public int size() {
            return size;
        }
 
        public long totalCopies() {
            return totalCopies;
        }
    }
}

And here it is producing exactly the counts the annotations claim — the complexity is measured, not asserted:

Complexity.sum(new int[] {1, 2, 3, 4, 5});        // 15
Complexity.sumPlusMax(new int[] {1, 2, 3, 4});    // 14   → 10 + 4, still O(n)
 
Complexity.pairComparisons(5);                    // 10       → 5·4/2
Complexity.pairComparisons(1000);                 // 499500   → the O(n²) blow-up
 
Complexity.halvings(1000);                        // 9
Complexity.halvings(1_000_000);                   // 19   → a million items, 19 steps
 
Complexity.linearSearch(new int[] {5, 3, 9}, 5);  // 0    → best case, 1 compare
Complexity.linearSearch(new int[] {5, 3, 9}, 9);  // 2    → worst case, n compares
Complexity.linearSearch(new int[] {5, 3, 9}, 7);  // -1   → absent
 
long[] calls = {0};
Complexity.fib(10, calls);                        // 55        (calls[0] == 177)
calls[0] = 0;
Complexity.fib(30, calls);                        // 832040    (calls[0] == 2692537!)
Complexity.fibMemo(50);                           // 12586269025  → O(n), no explosion
 
Complexity.IntList list = new Complexity.IntList();
for (int i = 0; i < 1000; i++) list.add(i);
list.size();                                       // 1000
list.totalCopies();                                // 1023  → < 2n, so O(1) amortized

That 2692537 next to 55 is the whole article in two numbers: a growth shape, not a stopwatch, decides whether fib(30) is instant or hopeless.

The interview corner

Big-O comes up in almost every technical interview, not as its own question but woven into every other one — "and what’s the time complexity?" is the follow-up you’ll hear the most. Here’s how to walk in ready.

Ask these before you commit to an answer:

• "Worst case, average, or amortized?" Naming the case is half the signal. Quicksort is O(n log n) average but O(n²) worst; an ArrayList append is O(1) amortized but O(n) for the one resize. Saying "which do you want?" shows you know they differ.
• "What’s the range of n, and are there constraints I’m missing?" An O(n²) solution is perfectly fine for n ≤ 1,000 and a disaster at n = 10⁶. The bound on n often tells you the target complexity — n ≤ 20 is quietly begging for an exponential/bitmask solution.
• "Should I count the output, or just the work?" Generating all subsets is O(2ⁿ) because the answer is that big, not because the algorithm is wasteful. Distinguishing "the work is expensive" from "the output is expensive" avoids a common mislabel.

The follow-up ladder — where a strong candidate keeps climbing:

1. "You said O(n) — prove it’s not O(n²) given that nested loop." Point at the inner loop’s bound: if the inner index only ever moves forward across the whole run (a two-pointer sweep), it’s O(n) total by the aggregate argument, not O(n²). Naming amortized aggregation here is the money move.
2. "Two inputs of different sizes — n and m." Don’t collapse them into one n. Merging two lists is O(n + m); a nested pair over them is O(n·m). Interviewers plant this to catch lazy single-variable answers.
3. "Reduce the space complexity." Time and space trade: the memoized Fibonacci is O(n) time but O(n) space — and you can drop it to O(1) space by keeping only the last two values, since that’s all each step needs. Show you can move along the time-space curve on demand.
4. "Amortize this." When a data structure has rare expensive operations (resize, rehash, tree rebalance), reach for the aggregate method: sum the total cost over n operations and divide. That’s how you justify O(1) amortized for a hash map’s put or a dynamic array’s add.
5. "Now it’s recursive — give me the complexity." Set up the recurrence: T(n) = 2·T(n/2) + O(n) is the merge-sort shape and solves to O(n log n); T(n) = T(n−1) + O(1) is a straight line, O(n); T(n) = 2·T(n−1) branches to O(2ⁿ). Reading the recurrence off the recursion tree is the skill they’re probing. (See the halving recursion in binary search.)

Three mistakes that fail the round:

• Multiplying loops that are sequential, or the worst case that can’t repeat. Two loops side by side add (O(n)); a rare expensive operation doesn’t multiply across the sequence (amortized O(1)). Both are the same error — charging a product where you should charge a sum.
• Confusing amortized with average. Amortized O(1) is a worst-case guarantee over a sequence; average O(1) is a probabilistic bet on inputs an adversary can break. Using them interchangeably signals you don’t actually know either.
• Keeping the constant when it’s the shape that’s asked, and dropping it when the seconds matter. O(2n) and O(500n) are both O(n) — say O(n). But when the interviewer asks which of two O(n) solutions is faster, "they’re the same Big-O" is the wrong answer; then the constant is the whole point.

Where to go from here

You now own the core: Big-O is a shape, not a stopwatch — count operations as n grows, drop the constants and lower-order terms, and read the shape straight off the code (sequential adds, nested multiplies, halving is log, recursion branches to its depth). Three natural next stops:

• Solving recurrences — the Master Theorem turns T(n) = a·T(n/b) + f(n) into a Big-O in one glance, which is how you analyze any divide-and-conquer algorithm without drawing the whole tree.
• Amortized analysis in depth — the banker’s and potential methods generalize the aggregate argument you saw here, and they’re what prove the near-constant bounds behind union-find and Fibonacci heaps.
• Space complexity and the memory hierarchy — an O(n) algorithm that thrashes the cache can lose to an O(n log n) one that stays in fast memory, because the "constant" Big-O drops hides a 100× gap between a cache hit and a trip to RAM.

Next time two apps do the same job and one crawls while the other flies, you won’t reach for a stopwatch. You’ll glance at how each one grows, name its shape, and know — before you run a thing — exactly which one falls off the cliff.