Complexity in Practice: Reading Constraints and Choosing an Algorithm

A problem statement ends with a line like 1 <= n <= 200000. Many people read it last, or skip it, and start coding the first idea that gives correct answers. That idea is often two nested loops over the input. On the sample it prints the right number. On the judge's largest test it runs out of time, and the verdict says nothing about why.

Two nested loops over 200000 elements are about n^2 / 2 = 2*10^10 steps. No time limit you will meet in a contest or an online assessment allows that. The same loops over 2000 elements are 2*10^6 steps and finish before you notice. The code is identical; the constraint decides whether it is a solution.

So the constraints line is a hint from the problem setter about which complexity they intend. Big-O notation is how you read that hint. It is not a grade for elegance: an O(n^2) solution is the right one when n <= 3000 and you can write it in five minutes with no bugs. This lesson shows how to turn constraints into a step budget, how to solve one problem at three different complexities, and how to count steps so that you see the difference instead of taking it on faith.

You need the C++ basics and the standard containers from STL & Algorithms. Everything else is built here.

The usual starting point is a rough budget: a time limit of one or two seconds buys on the order of 10^8 simple steps, where a step is something like an addition, a comparison or an array access. Antti Laaksonen's "Competitive Programmer's Handbook" puts it as "some hundreds of millions of operations in a second". Treat this as a rule of thumb for ordering your options, not as a fact about any particular judge: the real speed depends on the machine, the compiler, the memory access pattern and what one "step" actually costs.

From that budget comes the table used throughout this course. Each row is the complexity that typically fits when n is up to the given size.

The table is easier to trust once you evaluate it. This program computes the step count of each row at the top of its range, and of a few mismatches: the next-slower complexity at the same n.

Look at the gaps. Every fitting row lands between 10^6 and about 10^8, and the polynomial mismatches are off by a factor of several hundred or more. The factorial row shows the other way to miss: n! grows so fast that two more elements already overshoot. That is why the rule of thumb works despite being rough: you are not choosing between 10^8 and 2*10^8 steps, you are choosing between 10^7 and 10^10. A constant factor of 3 rarely changes the verdict; a wrong exponent always does.

Two more things to read in the constraints. The value range tells you the integer type: if values reach 10^9 and you add up to 2*10^5 of them, the sum reaches 2*10^14 and needs a 64-bit long long. And the number of test cases multiplies everything: "up to 10^4 test cases, each with n <= 2*10^5" usually comes with a promise that the sum of all n is bounded, and that sum is the n you budget for.

Here is a problem to solve three times.

Best stretch. A community bike-repair stand records its net balance for each of n days: positive when donations beat costs, negative otherwise. The treasurer wants the largest total over a stretch of consecutive days, at least one day long. Constraints: 1 <= n <= 2*10^5, each value between -10^9 and 10^9.

The input is n followed by the n daily values:

By hand: the stretch 3 -1 5 totals 7, and nothing beats it. Including the 4 -6 in front lowers the total; extending past 5 into -9 lowers it more; 2 2 makes only 4.

The first idea is to try every stretch [l, r] and add up its values: three nested loops, O(n^3). The second notices that the sum of [l, r + 1] is the sum of [l, r] plus one value, so a running sum removes the innermost loop: O(n^2). The third asks a different question. What is the best stretch that ends on day i? It is either day i alone, or day i appended to the best stretch ending on day i - 1, whichever is larger. One pass computes that for every i, and the answer is the best of them: O(n). This linear method is usually called Kadane's algorithm; Jon Bentley's "Programming Pearls" made the problem well known and credits the linear solution to Jay Kadane.

The constraints already chose for us: n up to 2*10^5 means O(n) or O(n log n). Every program in this course reads its input through a function solve(std::istream&, std::ostream&). The browser playground has no keyboard input, so main feeds solve the sample from a string. On a judge you call solve(std::cin, std::cout) instead and nothing else changes.

The values are stored as ll (long long) even though each one fits in an int, because the totals do not. The pitfall section below shows what happens otherwise.

A claim like "the cubic version is too slow" deserves evidence. Timing a program on a shared server gives noisy numbers that change from run to run. Counting does not: we decide what one step is, add one each time it happens, and print the totals for growing n.

Here a step is one addition of a day's value into a running sum. All three versions run on the same random data and must agree on the answer.

Each time n doubles, the last column doubles, the middle one multiplies by 4 and the first by almost 8. That is what the exponents mean, made visible. The exact counts are n(n+1)(n+2)/6, n(n+1)/2 and n: the cubic version has a small constant in front of n^3 (one sixth), and it still loses badly. Extrapolate the first column to n = 2*10^5 and you get about 1.3*10^15 steps. The middle column gives 2*10^10. Only the last one fits.

The cubic version is useless at the real limits and very valuable anyway. It is short, it follows the definition of the problem directly, and it is hard to get wrong. That makes it the reference for testing the fast version.

A stress test runs both on thousands of small random inputs and compares the answers. Small inputs matter: when the two disagree, the failing case is short enough to check by hand. The program below tests the correct linear version and a tempting variant that starts best at 0 instead of the first value. That variant is the right answer to a slightly different problem, one where an empty stretch with total 0 is allowed.

The bug is found on the third random case, and the counterexample is a single day with a loss of 7. Once you see it, the cause is obvious: when every value is negative, no stretch reaches 0, but the buggy version reports 0 anyway. The sample in the statement had positive totals and would never have shown this.

This habit, a brute force written first and kept for a stress test, is one of the most reliable ways to avoid a wrong answer that you cannot explain. The next lesson turns it into a reusable harness.

Two parcels, one drone. A courier has n parcels with weights w_1 ... w_n grams. A drone flight must carry exactly two different parcels whose weights add up to exactly C grams. Is there such a pair? Constraints: 2 <= n <= 2*10^5, 1 <= w_i, C <= 10^9.

Three approaches, in order of complexity:

1. All pairs. Check every i < j: n(n-1)/2 checks, O(n^2). Too slow at the limit.
2. Sort, then two pointers. Sort the weights, put one pointer at the lightest and one at the heaviest. If the two add up to less than C, the lightest one cannot be in any pair (even the heaviest partner is not enough), so move the left pointer right. If they add up to more, the heaviest one is out, so move the right pointer left. Each step discards one parcel, so there are at most n - 1 steps after an O(n log n) sort.
3. Hash set. Walk through the parcels; for each weight w, ask whether C - w was seen before, then remember w. That is n lookups and n insertions into a std::unordered_set, each constant time on average: O(n) expected.

The input is n and C, then the weights. This program solves the sample with the sorting method and then counts the work of all three methods on inputs with no valid pair, which is the worst case because nobody stops early.

The pointer column does not include the sort. std::sort and std::ranges::sort are required by the standard to make O(n log n) comparisons, so the sorting method costs O(n log n) in total; at n = 2*10^5 that is a few million comparisons. The pointer loop itself is an example of amortized reasoning: a single step can do anything, but since every step moves a pointer inward and the pointers start n - 1 apart, the whole loop takes at most n - 1 steps.

The hash set column looks like the winner, and on random data it is. But the word "expected" is doing work. std::unordered_set lookups are constant on average and linear in the size of the container in the worst case, which happens when many keys land in the same bucket. Which keys do that depends on the hash function, and for integers the standard library's hash is a fixed, public function. Someone who knows it can choose inputs that collide on purpose; Scott Crosby and Dan Wallach showed this as a practical denial-of-service attack on real hash table implementations in 2003. Contest platforms where other participants may supply test inputs against your solution are a version of the same situation.

So the honest summary of the two methods is: sorting with two pointers is O(n log n) in the worst case; hashing is O(n) expected and O(n^2) in the worst case. At n = 2*10^5, both fit in the budget when the hash behaves, and only the first one is guaranteed to. When O(n log n) fits, it is the safer choice. Lesson 10 returns to the problem of hashing that an adversary cannot predict.

std::vector::push_back is specified to take amortized constant time. Sometimes the vector is full, and that one call allocates a larger buffer and moves every element into it, which is O(n). Amortized constant means that over any sequence of n calls the total work is O(n), so the expensive calls are rare enough to average out.

They are rare because the capacity grows by a constant factor rather than a constant amount. The exact factor is the library's choice and differs between implementations. This program simulates both policies, doubling the capacity and adding one slot, and counts how many element copies each one causes for n insertions.

With doubling, the copies are 1 + 2 + 4 + ... up to the last capacity, which is less than twice the final size, so there are never more than two copies per element. With "plus one", every insertion copies the whole array and the total is n(n-1)/2. Same code, same answers, and one policy is quadratic.

The same reasoning tells you when a container is the wrong tool. If you know the final size, reserve it and there are no copies at all. If you insert at the front of a std::vector, every insertion shifts all existing elements, and no growth policy helps.

Big-O hides constant factors, and sometimes they decide. An O(n log n) algorithm with a heavy inner step can lose to a tight O(n^2) loop when n is a few dozen; for this reason the std::sort implementations in both GCC's libstdc++ and LLVM's libc++ hand short ranges to insertion sort, a quadratic method. At the sizes in the table, though, the exponent dominates, as the counting program showed: one sixth of n^3 is still hopeless at n = 2*10^5.

Memory has a budget too, usually stated next to the time limit. Do the arithmetic before you allocate. A std::vector<int> of 10^7 elements is 40 MB on the usual platforms where int has 4 bytes. A 5000 by 5000 table of long long is 2.5*10^7 entries of 8 bytes, 200 MB, which is more than many problems allow even though O(n^2) time is fine at that size. A table with an entry for each of the 2^20 subsets and each of 20 positions has about 2*10^7 entries: fine for int, worth checking for anything bigger.

The machine itself adds one effect worth knowing. Memory is fetched from RAM in blocks (cache lines), so walking through a contiguous array uses every byte it fetched, while following pointers in a std::list or a tree jumps to unrelated addresses. Both traversals are O(n); the contiguous one is often several times faster in practice. Prefer std::vector and arrays unless you need what a node-based container gives you.

In an interview the constraints are often not written down. Asking for them is part of solving the problem, not a delay before it. Good questions are short and specific:

• How large can the input get? Thousands, millions?
• What is the range of the values? Can they be negative, or zero? Can the answer overflow 32 bits?
• Can the input be empty? Are there duplicates? Is it sorted?
• Do you want the value, or also where it comes from (indices, the stretch itself)?

Then say a brute force out loud with its complexity, before optimizing: "Trying every pair is O(n^2), which is fine for a thousand parcels but not for a million. Sorting first gets it to O(n log n)." This shows that you can produce a correct answer, gives you a reference to test against, and often reveals the bottleneck that the better solution removes. When you finish, state time and extra memory separately, and say whether the time is worst case or expected.

Two original problems. Try each before reading the solution program.

Repeated tickets. A raffle printed n tickets, but the printer was faulty and some numbers repeat. Count the pairs of tickets i < j with the same number. Constraints: 1 <= n <= 2*10^5, numbers between 1 and 10^9. The limits rule out checking all pairs, and the answer can reach n(n-1)/2, about 2*10^10, so it needs long long. Sort, then every group of k equal numbers contributes k(k-1)/2 pairs: O(n log n).

Closest readings. Given n temperature readings in hundredths of a degree, find the smallest absolute difference between two different readings. Constraints: 2 <= n <= 2*10^5, readings between -10^9 and 10^9. After sorting, the closest pair is always adjacent, because any non-adjacent pair has an adjacent pair between them that is at least as close. The difference can be 2*10^9, just below the int limit of 2147483647. Slightly wider limits would overflow it, so the program uses long long rather than rely on that margin.

The program solves both samples and stress tests both solutions against an O(n^2) brute force.

1. In the step-counting program, add n = 1600 to the list. Predict all three counts from the doubling pattern before you run it. Then predict the cubic count at n = 2*10^5 from the formula n(n+1)(n+2)/6.
2. In the stress test, change the random values from rng.range(-10, 10) to rng.range(0, 10). Predict whether the buggy version is still caught, then run it. What does that tell you about choosing the range of random inputs?
3. In the parcel program, change the test data so that a valid pair exists near the start (for example make C equal to w[0] + w[1]). Which columns shrink, and which one does not shrink as much as you might expect?
4. In the growth simulation, add a policy that grows by a factor of 1.5 (c + c / 2, but at least c + 1). Predict whether copies per element stay bounded, and roughly by what.
5. Write a third practice problem's solution: given n <= 2*10^5 values, count the pairs i < j with a_i + a_j = C. Reuse the two-pointer idea, take care with groups of equal values, and stress test it against the double loop.