LetItCrash

How do you calculate a complexity budget?

LLM-authored, human-reviewed

Foundations Algorithms & theory

In this article

Before you write code, estimate how much work your approach will do on the largest input the problem allows. Then compare that with how much work you can afford. That comparison is a complexity budget. It tells you which ideas are worth writing before you spend an hour writing one that was never going to be fast enough.

You already do this every time you check whether you have time for one more thing.

Example 1: errands before the train

Your train leaves in 20 minutes. You want to pick up a coffee, a parcel and a prescription, and each stop takes about 8 minutes.

You do not need to walk into the first shop to know how this ends. Three stops at 8 minutes is 24 minutes, and you have 20. Two stops fit. The third one does not, unless something changes: one shop is closer, or the parcel can wait until tomorrow.

That is a complexity budget, done in your head in a few seconds:

  • What you can afford: 20 minutes.
  • What each piece costs: about 8 minutes per stop.
  • How many pieces: three stops.
  • The verdict: over budget, so change the plan before you start, not on the platform.

Without the budget. You start with the coffee, then the parcel, and you are halfway through the pharmacy queue when the train leaves. Every stop went fine. The plan was too big from the beginning.

Example 2: handshakes at a party

Some plans grow faster than you expect. At a small dinner, everyone shakes hands with everyone else. Count the handshakes:

Guests Handshakes, if everyone greets everyone
4 6
10 45
100 4,950
300 44,850

Ten times the guests means about a hundred times the handshakes. Each new guest has to greet everyone who is already there, so the work grows with the guests times the guests.

Anyone who has been to a wedding knows this without counting. Nobody tries to greet all 300 guests personally. The couple walks from table to table instead. That knowledge comes from experience. The invitation only tells you that 300 people are coming.

Code is full of handshakes. Whenever every item is compared with every other item, the work grows like this table.

The Mockratis Machine

To budget, you need a price list. Real computers differ, so the coding exercises on this site run on an imaginary computer called the Mockratis Machine. Every operation has a fixed price, and every call to your function has a fixed time limit:

Operation Cost
Simple op (arithmetic, comparison, assignment, branch, reading a variable or tuple field) 1 ns
Function call and return 5 ns
Allocating a list cell or small object 10 ns
Map or set lookup or insert 50 ns
Copying or concatenating n items n × 1 ns
Time limit per call 10 ms (about 10 million simple operations)

10 ms is 10,000,000 ns, so at 1 ns per simple operation, your budget for one call is about ten million simple operations.

The price list also shows that “one operation” is not one size. One map lookup costs as much as 50 comparisons. Copying a 10,000-item list once costs 10,000 ns, which is cheap. Copying it once for each of its 10,000 items costs 100 ms, which is ten times the limit.

The prices are a model, not a measurement, and they are the same for every learner and every exercise. The site does not time your code in nanoseconds: the real test runner only stops code that runs for several seconds. The Machine is a shared ruler for estimating, so that “fits the budget” means the same thing everywhere.

Example 3: Two Sum, in Lua

Here is the plain Two Sum solution from How to start solving a problem?: check every pair with two loops.

function two_sum(nums, target)
  for i = 1, #nums do
    for j = i + 1, #nums do
      if nums[i] + nums[j] == target then
        return {i, j}
      end
    end
  end
  return {}
end

It passes every example in the problem, and the examples have four numbers or fewer. Now put it on the largest list the problem allows. The Two Sum constraints say nums has between 2 and 10,000 numbers, so budget for 10,000.

How many pairs does the code check? It is the handshake table again. With 10,000 numbers, and no pair that adds up until the very end, the inner line runs 49,995,000 times. You do not have to trust the formula. Add a counter and run it:

local checks = 0
for i = 1, #nums do
  for j = i + 1, #nums do
    checks = checks + 1
  end
end
print(checks)   -- 49995000 for a list of 10,000 numbers

Counting the work by running it is a move of its own on this site: timing evidence.

Now price it on the Machine. Even at the cheapest price, 1 ns per check, 50 million checks is 50 ms. The budget is 10 ms. The two loops are at least five times over budget, before counting the addition and the comparison inside each check.

The faster version keeps a notebook, a table called seen, of every number it has passed:

local seen = {}
for i, value in ipairs(nums) do
  local complement = target - value
  if seen[complement] ~= nil then
    return {seen[complement], i}
  end
  seen[value] = i
end

It visits each number once. Each visit does one lookup and one insert in the notebook, at 50 ns each. For 10,000 numbers that is 10,000 × 100 ns = 1,000,000 ns, or 1 ms, plus a little for the simple steps. It fits in the 10 ms budget with plenty to spare.

Both versions give the same answers. Only the budget tells them apart.

Without the budget. You write the two loops, run the examples, and every one passes. Today, that may be the end of it: most exercises on this site only test small inputs. But give the same code a list of 10,000 numbers and it runs far past its budget. Nothing in your code is wrong. The plan was too big from the beginning, like the third errand. The budget is how you find that out before real data does.

Where the numbers come from

A budget needs two numbers: how big the input can get, and how much work your approach does per item. Like the cues in a cue scan, they come from three places.

  • Stated. When a problem states its limits, such as “up to 10,000 numbers,” that is the number to budget for. Read it before you write code. When it does not, ask what a realistic large input would be.
  • Shown, and misleading. The examples are tiny on purpose, so they are easy to read, and four numbers make every approach look instant. This is the main difference from a cue scan, where the examples are some of your best cues. For the budget, the examples hide the cost.
  • Experience. Knowing that comparing everything with everything gets slow, and roughly when, comes from having watched a program crawl. The wedding couple did not count the handshakes. They had been to weddings before.

Borrowed experience: a table of sizes

If you are new to this, you will not have that experience yet. Here is some to borrow. The table shows how fast each kind of plan grows as the input grows ten times:

Input size One pass over the items Every pair, like the handshakes
100 100 4,950
1,000 1,000 499,500
10,000 10,000 49,995,000
100,000 100,000 4,999,950,000

Multiply the input by ten, and one pass does ten times the work, but checking every pair does about a hundred times the work. That is why an approach can feel instant on an example and run out of time on the largest test.

With a budget of about ten million simple operations, the table gives a rough guide:

  • Up to about 1,000 items, checking every pair fits: about half a million checks.
  • Around 10,000 items, checking every pair does not fit any more: about 50 million checks. One pass fits easily.
  • Around 100,000 items and up, only plans that look at each item a few times fit, such as one pass, or sorting the list once first.

These are someone else’s rough experience, written down. Use them to choose which idea to try first, not as rules.

You can also work out the budget per item: divide the budget by the input size. Ten million operations across 10,000 numbers is 1,000 per number. The notebook version spends about 100 per number. The two loops spend about 5,000 per number on average, because each number is checked against about half of the others.

Memory, and time, in the real world

So far the budget has been about time: how much work happens. Memory is the other half: how much you have to hold at once.

Think of a delivery van. Ten thousand parcels delivered over many trips never need to fit in the van together. But if your plan is to load every parcel before leaving, they all do.

The notebook version of Two Sum holds up to 10,000 entries at once. That is fine. A plan that builds a table with an entry for every pair of 10,000 numbers holds about 50 million entries, and that usually is not.

Most algorithm exercises, on this site and elsewhere, care mostly about time and give memory little attention. That is a convention of algorithm practice, so you can focus on one thing at a time. Real software is different. Memory costs money, a phone has far less of it than a server, and a program that runs out of it does not run slowly. It crashes.

Time changes meaning in the real world too. In an exercise, “fast” means “fits the budget.” For a person using your app, fast means an answer before they lose interest, which can be a second or two. A plan that visits each item once sounds good, but if there are a hundred million items, one visit each can still take far too long. The fix is then usually not a cleverer loop. It is a different design:

  • Do the work ahead of time. Build an index once, like the index at the back of a book, so each search looks up an answer instead of reading every page.
  • Do the work at the same time. Split the items into eight parts and search all eight at once, on eight processor cores. The total work is the same, but the wait can drop to about an eighth. This is concurrency, and it is what this site is built around: the BEAM, the machine Elixir and Erlang run on, makes it cheap to run many small processes at once. What the BEAM actually is explains how.

The habit is the same either way. Ask what you can afford, whether that is ten million operations, a few gigabytes, or two seconds of someone’s attention, and check the plan against it before you build it.

How the budget feeds the other moves

The complexity budget is one of several moves this site uses to describe solving a problem. To see the moves in order on Two Sum, follow How a strong solver approaches Two Sum.

Cue scan: the size limit is a cue

The cue scan finds the input size in the constraints. The budget turns that size into a hint about what kind of solution the problem expects.

Two Sum says up to 10,000 numbers. Every pair is about 50 million checks, so the size tells you to look for something that visits each number about once.

Now change one word. The cue-scan article showed what happens when “two numbers” becomes “any group of numbers” that adds up to the target. That problem is much harder, and its limits are usually much smaller. Here are two versions with different limits:

  • Up to 16 numbers. There are 65,536 possible groups. Adding up 16 numbers for each group is about a million steps. That fits, so the small limit is telling you that trying every group is fine.
  • Up to 100 numbers, each between 1 and 100, target up to 10,000. Trying every group now means more than a million trillion trillion groups, which no computer will ever finish. But the totals can only be between 0 and 10,000. So you can keep one table entry for each possible total and, for each of the 100 numbers, update the whole table: 100 × 10,001, about a million updates. That fits too. This technique is called dynamic programming.

The wording is the same in both. Only the limits differ, and they point at different solutions. If you are new to this, you are not expected to come up with the table on your own. The point is smaller: an unusually small limit, or a limit on the values as well as the count, is a cue. The budget is how you read it.

Hypothesis: the budget makes a shortlist

A hypothesis is a guess at an approach. The budget can rule a guess out before you write it. For Two Sum at 10,000 numbers, here are three guesses and their prices:

Guess Rough work Verdict
Check every pair about 50 million checks too big
Sort the list, then walk in from both ends (two pointers) about 130,000 comparisons to sort, plus 10,000 steps fits
Keep a notebook of numbers seen 10,000 lookups and inserts, about 1 ms fits

Both survivors are affordable, but the budget does not say they are correct. That is the next move’s job.

Counterexample hunt: try the biggest, worst input

The counterexample hunt usually looks for tricky small inputs. For the sorting guess it finds one quickly: sorting moves the numbers, and Two Sum asks for their original positions. So you would have to carry each position along while you sort. That is a correctness problem, not a budget problem.

For speed, the counterexample is a big input, and it has to be big in the worst way. In the examples, the matching pair is near the start, so even the two loops stop almost at once. Build a list where the only matching pair is the last two numbers:

local nums = {}
for k = 1, 9998 do
  nums[k] = k            -- 1, 2, 3, ..., 9998: no two of these add up to 300000
end
nums[9999] = 100000
nums[10000] = 200000     -- 100000 + 200000 is the only pair that works
local target = 300000

On this list, the two loops check all 49,995,000 pairs before they find the answer at positions 9999 and 10000. A big list that happens to have its answer near the start would not show the problem.

Implement: watch for hidden loops

While you implement, the cost can hide inside a helper. Here is a Two Sum that looks like it has only one loop:

local function index_of(list, value)
  for k = 1, #list do          -- this is the hidden second loop
    if list[k] == value then
      return k
    end
  end
  return nil
end

function two_sum(nums, target)
  for i = 1, #nums do
    local j = index_of(nums, target - nums[i])
    if j ~= nil and j ~= i then
      return {math.min(i, j), math.max(i, j)}
    end
  end
  return {}
end

It passes the examples. But index_of reads through the list each time it is called, and two_sum calls it once for every number. On the worst list above it does about 100 million looks, twice as many as the two loops, because it searches the whole list every time instead of only the numbers after i. The notebook version does the same job with one table lookup instead of a call to index_of.

When you price your code, count the loops inside the functions you call, not only the loops you can see.

Timing evidence: measure the growth

When you are not sure of an estimate, run it. The counter in the Two Sum example turned a guess into a number. You can also time the code at two sizes, ten times apart:

local start = os.clock()
two_sum(nums, target)
print(os.clock() - start)   -- seconds of processor time

On one laptop, the two loops took about 0.009 seconds on the worst list of 1,000 numbers and about 0.9 seconds on the worst list of 10,000. Ten times the input took about a hundred times as long, which is the handshake table’s pattern. Your times will differ. Look at the ratio.

You will misjudge budgets, and that is fine

Your estimates will be rough, and they only need to be. Being off by a factor of two almost never matters. Being off by a factor of a thousand always does. The budget is for telling a plan that fits easily from one that is hopeless, not for predicting the exact time. In xkcd 2205, “Types of Approximation”, an engineer keeps an error under 1 part in 1,000, while a cosmologist agrees to round pi to ten. A complexity budget is closer to the cosmologist.

You will also miss hidden costs at first: a lookup that is not as cheap as it looks, or a copy inside a loop. When a test runs out of time, ask which part of the work grew faster than you expected, and write it down. That is the Retrospect move, and it is how the table of sizes becomes your own experience instead of someone else’s.

Every exercise on this site has a known solution, built from well-known techniques. So if your estimate comes out a hundred times over, the budget is not telling you the problem is impossible. It is telling you to look for another route, the way the notebook replaced the two loops. Some problems, like trying every group of numbers, have no known route that stays fast for every input; P vs NP explains why. Problems like that usually come with a small input limit, and, as the cue scan section above showed, the small limit is itself a cue.

Write it down before you code

Before you write code, fill in one line:

The largest input is . My plan does about work per item, so about in total. The budget is about ten million simple operations, so this looks comfortable / borderline / too big. I will try .

For Two Sum:

The largest input is 10,000 numbers. Checking every pair does about 50 million checks in total. That is at least five times the budget, so I will try the notebook version: one pass, about 100 ns per number.

If you cannot fill in the line, go back to the constraints. If you can, you know which idea to write first.

← Back to articles

Exercises