Read n, and You Know What to Write: Time Complexity and the Maximum Subarray Sum

A new series: reading Antti Laaksonen’s Competitive Programmer’s Handbook (CPHB). It’s the companion text to the CSES Problem Set, the PDF is free online, and its thirty chapters run from complexity all the way to geometry — thin, dense, no filler.

There is no shortage of CPHB notes and solutions on the web. This series tries to do three things differently:

1. Every post starts from the brute-force solution and asks what it wastes. A faster algorithm is almost always one that noticed a structure the brute-force solution never used. That’s the thread running through the whole series.
2. Every post has an animation you can drive yourself. Step forward, step back, change the input and rerun. A static picture can only give you the conclusion; an animation lets you see exactly where a step gets saved.
3. Every post has a section called “where this shows up at work”, tying the contest technique back to Production — when it connects, and saying so plainly when it doesn’t.

Part one is the foundation of the whole book: time complexity, and the classic problem the book uses to show it — the maximum subarray sum.

How much can you do in one second

Time complexity is the tool for estimating how fast an algorithm is: write the number of basic operations as a function of the input size $n$, keep only the largest term, ignore constants.

The estimate rests on a single number: a modern computer does a few hundred million basic operations per second. With that number you can judge a solution before writing it. One-second limit, $n = 10^5$, and the approach you have in mind is $O(n^2)$ — that’s $10^{10}$ operations, tens of seconds. You know it won’t work before writing a line.

Run it the other way and it’s even more useful: read $n$, and you can infer the complexity the problem wants.

The book is written in C++, and the table is calibrated for C++ speed. This series writes its code in Python — CSES accepts Python 3 and PyPy3 — so keep in mind that Python’s constant factor is more than an order of magnitude worse than C++‘s: in the same second, budget around $10^7$ operations, push every $n$ in the table down a notch, and treat $O(n^2)$ as safe only up to about $n \le 2000$.

This table is the first thing a contestant does with a problem. An $n \le 20$ is a hint that “you may enumerate subsets”; an $n \le 10^6$ says “sort or scan — and those are the only two roads”. It rules out half the ideas on the spot.

But keep the book’s own caveat in mind: complexity is only an estimate, and it hides the constants. Two $O(n)$ algorithms can do $n/2$ operations or $5n$ — a tenfold difference once you run them.

How to work out the complexity

The calculation rules from the book’s Ch2 boil down to four:

Shape of the code	Complexity	Example
$k$ nested loops, each running $n$ times	$O(n^k)$	two loops comparing every pair → $O(n^2)$
Several blocks one after another	the slowest block wins	$O(n) + O(n^2) + O(n)$ → $O(n^2)$
Two input sizes	write both	outer loop over $n$, inner over $m$ → $O(nm)$
Recursion	number of calls × cost per call	calls itself once, $n$ levels deep → $O(n)$; calls itself twice → $O(2^n)$

The example: maximum subarray sum

Given an array, find the contiguous run with the largest sum. The book’s example:

$[-1,\ 2,\ 4,\ -3,\ 5,\ 2,\ -5,\ 2]$

The answer is 10, from $[2, 4, -3, 5, 2]$ — you swallow the $-3$ in the middle because the two sides together outweigh it. The problem is only interesting because the array has negatives. The book allows the empty subarray, so the answer is at least 0.

There are three solutions, at $O(n^3)$, $O(n^2)$ and $O(n)$. All three are looking at the same object: every subarray, laid out as a triangle.

Algorithm 1: O(n³), each range summed from scratch

The most direct approach: fix the two ends a and b, then use a third loop to add up array[a..b].

best = 0
for a in range(n):
    for b in range(a, n):
        sum = 0
        for k in range(a, b + 1):
            sum += array[k]
        best = max(best, sum)

What it wastes: when it computes array[0..3], it had array[0..2] a moment ago — and throws that sum away to add everything up again.

Algorithm 2: O(n²), extend along the row

Reclaim what was just thrown away: $\text{sum}(a..b) = \text{sum}(a..b-1) + \text{array}[b]$. Every time the right end moves one cell, add one number. The third loop disappears.

best = 0
for a in range(n):
    sum = 0
    for b in range(a, n):
        sum += array[b]
        best = max(best, sum)

What it still wastes: it visits every cell in the triangle. But for a given right end b, all we care about is “the best sum that ends at b” — the other starting points don’t need a look.

Algorithm 3: O(n), Kadane

Ask a different question: what is the maximum subarray sum ending at position $k$? There are only two possibilities:

1. the subarray is array[k] alone;
2. it’s some subarray ending at $k-1$, followed by array[k] — and since we want the maximum, that subarray had better be the best one ending at $k-1$.

So each cell only needs a comparison against the previous cell’s answer:

best = sum = 0
for k in range(n):
    sum = max(array[k], sum + array[k])
    best = max(best, sum)

sum is “the best sum ending at $k$”; best is the largest one seen so far. (Don’t name a variable sum in real code — it shadows Python’s built-in; it’s kept here only to line up with the book.) One loop, $O(n)$. It’s also the best possible — any solution has to look at every element at least once. (The algorithm became famous through Jon Bentley’s Programming Pearls, which credits it to J. B. Kadane.)

Run it yourself: brute force versus Kadane

Below, Algorithm 2 and Kadane run side by side, on the same clock — each step is one addition on each side. Step through with ”→” or hit play; swap in your own array, or hit “Random”.

At $n = 8$ it’s 36 against 8, which doesn’t look like much. But brute force costs $n(n+1)/2$ additions — about $5 \times 10^9$ at $n = 10^5$. Kadane is still $10^5$.

If you want to see slowly why Kadane is right, the one below runs Kadane alone, with each cell split into two steps: first “extend or start over”, then “update best or not”. Watch the cell right after sum goes negative — that’s the moment “the running sum is negative, so adding to it only makes things worse”.

The book’s measurements

The book ran random inputs on one machine (input-reading time excluded):

$n$	Algorithm 1 $O(n^3)$	Algorithm 2 $O(n^2)$	Algorithm 3 $O(n)$
$10^2$	0.0 s	0.0 s	0.0 s
$10^3$	0.1 s	0.0 s	0.0 s
$10^4$	> 10.0 s	0.1 s	0.0 s
$10^5$	> 10.0 s	5.3 s	0.0 s
$10^6$	> 10.0 s	> 10.0 s	0.0 s
$10^7$	> 10.0 s	> 10.0 s	0.0 s

At small $n$ all three are equally fast — the gap in complexity only shows itself once $n$ grows. Which is exactly why small test data never catches a performance problem.

What got wasted

Line the three up and every speed-up is one piece of waste reclaimed:

• 1 → 2: adjacent ranges differ by one number; don’t recompute.
• 2 → 3: a given right end only needs its best starting point; don’t look at the others.

Both reclaim the same kind of structure — the answer to a subproblem can be reused. This series tags it [overlap], and part 6, dynamic programming, turns that one observation into a whole method.

Where this shows up at work

• Estimate before you write. A batch job that compares “every pair” is one second on a thousand rows and several days on ten million. The same table applies inside SQL: a self-join with no equality condition is two nested loops, and reading the execution plan is really reading the complexity.
• Constants bite. The constant that complexity hides is, in Production, very often a network round trip. A loop that hits the database once per iteration is still $O(n)$, and several orders of magnitude slower than one query that brings everything back — complexity can’t see that gap; you have to measure it.
• Checking someone else’s solution. An AI will hand you an accepted solution in no time; whether it times out at $n = 10^5$ is the reviewer’s question to answer. Holding the problem’s $n$ against the table above is the cheapest first check there is: no need to run anything, and you already have evidence for whether it passes. That’s the craft of reviewing AI code, applied to algorithms.

Practice

• CSES Maximum Subarray Sum: note that CSES requires a non-empty subarray. When every element is negative the answer is the largest negative, not 0 — so best can’t start at 0.

Reflections

Where I stand relative to competitions

Let me be clear about where I’m coming from: I have no real competition background — I didn’t come up through IOI or ICPC. What I have is LeetCode: around 1,500 problems solved over the years, and one weekly contest where I finished in the top 50. So this isn’t “a contestant teaches you to grind”; it’s someone who solved a lot of problems and then spent many years building backends, going back to reread this book and see what actually stuck.

What stuck the most is exactly what this post is about: see the size of the data, and run the numbers in your head first. Nothing deep about it, but it’s the one I use every single day.

What I use most at work is estimation

Day-to-day development rarely calls for writing an algorithm yourself — sorting, hash tables, indexes, the language and the database have them covered. But “will this computation finish?” comes up every day, and the answer almost always starts from how many rows the table has: this table is a few million rows today and tens of millions next year, this piece of logic scans it so many times, and does it pair up against that other table — plug those numbers in and you know whether the approach takes seconds, minutes, or never finishes. The thinking behind the table above holds just as well with row counts in place of $n$.

The one time I did implement an algorithm myself at work was a local prefix search over phrases on mobile, built on a compressed trie. That story waits for part 24, on strings; the point here is that the first question that project had to answer is the same one as this post’s — how big is the data, how much time does each query get, and therefore which structure can we afford.

What I look for as an interviewer

When I set algorithm questions as an interviewer, they’re not hard ones; most candidates solve them. Because what I’m looking at isn’t “did they solve it” but the details of how they got there: how they discuss the problem with me, how they pin down the conditions, how they interact when they get stuck, and whether what they write has taste. A problem nobody can solve shows me none of that.

It’s the same thing as the table above: the problem itself isn’t the point — the reaction right after seeing $n$ is. Do you pause, work out what this size allows, and only then start typing? That reaction is visible in an interview, and even more visible at work.