Estimating from constraints

Why this matters

Many coding problems state a limit on the input. The problem says the list has at most 10^5 numbers, or the string has at most 10^6 letters. That limit is a hint about the approach you should use. If you pick an approach that does too much work for that size, the program is correct on small tests and then runs out of time on the large ones. Online judges report this as "Time limit exceeded" on a specific test, and real services show it as a page that hangs.

This lesson gives you a method. You read the limit, write the number of steps each candidate approach needs as a formula, compare that number with a budget of steps that a computer can run in one second, and then pick the simplest approach that fits. You do not need a stopwatch to do this. You do need a rough idea of how many steps a second your machine can run, and the next section shows how to find that out.

The lesson uses the growth-rate ladder from the "Common growth rates" lesson in this module. It assumes you know what O(n) and O(n^2) mean. If not, read that lesson first.

What a step is and how many fit in a second

A step is one simple operation: adding two numbers, comparing two values, reading one array cell, or moving to the next item in a loop. Counting steps is rough work. A loop body that does one addition is about one step per pass. A loop body that builds a new string is many more steps, but for a first estimate you count the loop passes and treat each pass as a small fixed amount of work.

The number of steps a second depends on the language, the machine and what the loop does. You can measure it. Here is a Python loop that adds numbers from 0 up to n:

n= 1,000,000  result=499999500000  seconds=0.02
n=10,000,000  result=49999995000000  seconds=0.19

The code runs about 10 million passes in 0.19 seconds, so about 5 × 10^7 passes a second. The call time.perf_counter() returns a clock reading in seconds with fine precision. Taking the difference of two readings gives the time the work took. The :>10, in the print line is formatting: it right-aligns the number in 10 characters and adds commas, which makes the output easy to read.

The same kind of loop in C++ is much faster. This program does the same job with a volatile variable. The word volatile tells the compiler to read and write the variable on every pass, so it cannot skip the work. That makes each pass a little slower than a plain loop, so the number below is a fair, cautious figure for a loop that does real work.

n=100000000 total=4999999950000000 seconds=0.023
n=1000000000 total=499999999500000000 seconds=0.292

This was compiled with g++ -O2 (g++ 15.2.0 on the machine that wrote this lesson). The run time for 10^9 passes varied between 0.22 and 0.29 seconds across two runs, so the numbers are rough. The lesson uses them only to set a budget.

From these measurements you can set two budgets for the rest of the lesson:

• For a compiled program (C++ or Java) doing a few simple operations per pass, plan for about 10^8 steps in one second. Java runs faster than this for simple loops, so 10^8 leaves room for the other work in your program.
• For a Python loop, plan for about 2 × 10^7 steps in one second, because a Python loop with real work in it runs well below the 5 × 10^7 passes measured above.

These are rules of thumb. A judge machine may be slower than your laptop, and a loop whose memory reads miss the cache (the cache is a small, fast memory close to the processor) can be much slower. The budget is a line to compare against, not a promise. If your count is 10 times over the budget, the approach is too slow. If it is within a factor of two, check it more carefully.

Step 1: write the step count as a formula in n

Start with the simplest approach that answers the problem. Count how many passes its loops make, as a formula in n, the size of the input.

Take this question: is there a pair of different positions in a list where the two numbers add up to a target value? The simplest approach checks every pair. Each pair is one comparison. With n numbers, the number of pairs is n times (n - 1) divided by 2. In words: the first number can be paired with n - 1 others, the second with n - 2 others, and so on, and each pair is counted once.

For n = 10^5, that is 10^5 times 99,999 divided by 2, which is 4,999,950,000. That is about 5 × 10^9 comparisons. The budget for a compiled program is about 10^8 steps a second, so this approach would need about 50 seconds even at that rate. It does not fit.

You do not need the exact count to decide. You need the order of size: 5 × 10^9 is fifty times the budget, so the answer is clear. When the answer is close to the budget, you need the exact count and the constant factor, which is the number multiplied in front of the formula.

Step 2: compare the count with the budget

Now turn the limit into a table of what fits. The table below uses the compiled budget of about 10^8 steps. For each limit on n, it lists the largest growth rate that fits, with the step count at the top of the limit.

Read the table this way. Find the row for your limit. Any approach whose step count at the limit is at most the budget is a candidate. Pick the simplest candidate, write it, and check it against the examples.

The n^3 row is borderline in practice. 400^3 is 6.4 × 10^7, which is under the budget, but a loop body with more than a few operations pushes it over. A safer choice at that size is n^2 if you can find it. The table also hides constant factors on purpose. Two nested loops with a dictionary lookup (a table that finds a value from its key) inside each pass are not the same as two nested loops that add numbers.

Notice what the table does not say. It does not say that an approach with a bigger step count is wrong. It says it will be too slow for that size. A solution that uses n^2 steps for n up to 100 is fine. The same solution for n up to 10^5 is not.

Worked example 1: pairs that add to a target

The problem: given n numbers and a target value, decide whether any two different positions add up to the target. The limit is n at most 10^5.

The simplest approach is the one from Step 1, which checks every pair. Here is the check for real. The code below runs the pair check on a random list and counts the comparisons. The first function checks every pair. The second makes one pass and asks, for each number, whether the number that would complete the pair has been seen already. A set is a collection that answers "is this value here?" quickly. The hash table lesson in this module explains how a set achieves that.

brute n= 1000  pairs checked=   499,500  found=False  seconds=0.018
brute n= 2000  pairs checked= 1,999,000  found=False  seconds=0.077
brute n= 4000  pairs checked= 7,998,000  found=False  seconds=0.307
set   n= 1000  lookups=     1,000  found=False
set   n= 2000  lookups=     2,000  found=False
set   n= 4000  lookups=     4,000  found=False
set   n=100,000  lookups=100,000  found=False  seconds=0.021
n(n-1)/2 for n=100000: 4999950000

Look at the brute-force rows first. Doubling n from 2000 to 4000 multiplies the pairs checked by four: 1,999,000 becomes 7,998,000. That is the n^2 growth at work, and the measured time grows in the same way.

The brute-force run for n = 4000 took 0.307 seconds, and it checked 7,998,000 pairs. That is about 2.6 × 10^7 pairs a second in Python. At that rate, n = 10^5 needs 4,999,950,000 pairs, which is about 190 seconds. Your machine will give a different number, but the order of size will be the same: minutes, not a second.

The set approach checks each number once. For n = 100,000 it made 100,000 lookups and took 0.021 seconds. The step count grows in a straight line with n, so it fits the limit easily.

The choice is clear from the counts: n^2 for brute force, which fails at 10^5, and n for the set approach, which fits at 10^6 and beyond. This example also shows why you should never judge speed only from small tests. At n = 1000 the brute force took 0.018 seconds, which looks harmless.

Worked example 2: a limit of 10^6, all primes up to n

The problem: list every prime number from 2 up to n, where n is at most 10^6.

A prime is a whole number greater than 1 that has no divisor other than 1 and itself. The first idea most people try is trial division. For each number x, test whether any number from 2 up to the square root of x divides it. If none does, x is prime. This is a fair approach for one number. Count what it costs for all numbers up to n.

For a number x, the loop tests about the square root of x divisors in the worst case. Adding this over all x from 1 to 10^6 gives a total near 6.7 × 10^8 tests. That is almost seven times the compiled budget, and about thirty times the Python budget. Trial division for every number up to 10^6 does not fit.

The sieve of Eratosthenes avoids this. It keeps a list of flags, one per number. It starts with all numbers marked as possible primes. For each prime p it finds, it marks p times p, p times p plus p, and so on, as not prime. The total marking work is a few million steps for n = 10^6, far below the budget. The code below uses the sieve and also prints the trial-division count for comparison.

sieve n=  100,000  primes=  9,592  seconds=0.002
sieve n=1,000,000  primes= 78,498  seconds=0.028
trial division, worst case, all numbers to 10^6: 666,167,500 steps

The sieve found 78,498 primes up to 10^6 in about 0.03 seconds. The timing will differ on your machine, but the shape is clear: a sieve is very fast here because its work is a small multiple of n.

The trial-division number is the sum of the square roots of 1 to 10^6, using math.isqrt, which gives the whole-number square root. The output says 666,167,500 steps. This is an upper bound, because a composite number stops the test early once a divisor is found. Even so, the bound is far above the budget, which is why the choice of approach matters at this limit.

The lesson for the table is this: a limit of 10^6 does not always mean an n or n log n approach. It means the approach must do n-ish work in total. Trial division does roughly n times the square root of n, which is 10^9 at the top of the range, and that is what breaks the limit.

Worked example 3: one large number, and why square roots matter

Sometimes the input is a single number, not a list. The limit might be x at most 10^12 or 10^18. Then the work is not counted over a list, but over the size of the number itself.

Trial division for one number x uses about the square root of x tests. For x up to 10^12, the square root is 10^6, so the test takes at most a million divisions. That fits the budget comfortably. For x up to 10^18 the square root is 10^9, which is ten times the compiled budget, so the same method is too slow.

The code below checks two numbers. The first is 10^9 + 7, which is a well-known prime. The second is 10^12 + 39, which is also prime. The function counts the divisions it tries.

x=1,000,000,007  prime=True  divisions=31,621
x=1,000,000,000,039  prime=True  divisions=999,999

The loop stops at the square root because any divisor larger than the square root pairs with one smaller than it, and the smaller one would have been found already. For 10^9 + 7 the loop made 31,621 divisions, which is the square root of 10^9 (about 31,623). For 10^12 + 39 it made 999,999 divisions, which is just under the square root of 10^12. For a prime, the number of divisions is about the square root of x, and this is the fact the whole estimate rests on.

Now apply the table. A limit of x up to 10^12 allows a square-root approach, because 10^6 steps is far below the budget. A limit of x up to 10^18 does not, because 10^9 steps is ten times the compiled budget. For that limit you need a different method, such as the Miller-Rabin test, which checks a number with a small fixed number of rounds of arithmetic. That test is beyond this lesson, but the constraint tells you that a square-root approach is not enough.

This example shows that the limit can be on the value of the input, not on how many items it has. The step count depends on what the limit applies to. Read the problem to see whether n is a list length, a value that gets looped over, or a number that gets processed in some other way.

Common mistakes

Reading a limit on values as a limit on loops. The problem says each number is at most 10^9. It does not say you can loop from 1 to 10^9. A loop from 1 to 10^9 in Python takes far longer than the budget, and in C++ or Java it is ten times the compiled budget. Check whether the limit applies to the count of items or to the size of a value.

Forgetting that the limit may cover several test cases together. A problem may say there are up to 10^4 test cases, and the total of all n over the test cases is at most 2 × 10^5. The total is the limit that matters for the worst case, but it is easy to read the per-test limit and forget the total. A single test with n = 2 × 10^5 still breaks an n^2 approach, because 2 × 10^5 squared is 4 × 10^10.

Counting the loops but not the work inside them. A loop over n items that calls x in some_list on each pass scans the list each time. That makes the total n times n, even though the code only shows one loop. In Python a list membership test is itself a loop over the list. Use a set for lookups when the limit is large.

Using the budget without measuring it. A Python program that does 10^8 steps does not finish in one second. At the measured rate of about 5 × 10^7 simple passes a second, 10^8 passes take about two seconds on this machine. Use the Python budget for Python code, not the compiled budget.

Off-by-one errors at the limit. If the problem says n is at most 10^6, make the array size 10^6 + 1 or index from 1 carefully. The error below comes from an array one size too small. The code asks for index 10 of a list with ten items, which only has indexes 0 to 9.

Traceback (most recent call last):
  File "/path/to/main.py", line 2, in <module>
    print(flags[10])
          ~~~~~^^^^
IndexError: list index out of range

The File line shows the path of the file that was run, which will differ on your machine. The message names the line and the index. The fix is to size the list to the largest index you need, which is n + 1 when indexes run from 0 to n. The sieve in the second example allocates n + 1 entries for this reason.

Practice

Exercise 1. The limit is n at most 2 × 10^5, and your plan checks every pair of items. Does it fit the compiled budget? Which growth rate would you need instead?

Show the answer

Checking every pair takes n times (n - 1) divided by 2 steps. For n = 2 × 10^5 that is about 2 × 10^10, which is about two hundred times the compiled budget. It does not fit. A growth rate of n log n fits: 2 × 10^5 times about 18 is about 3.6 × 10^6 steps. A set-based single pass, which is order n, fits too.

Exercise 2. The limit is n at most 60, and your plan tries every subset of the n items. Does it fit? If not, what is the largest polynomial that fits?

Show the answer

There are 2^60 subsets, which is about 1.15 × 10^18. That is far too many. A polynomial growth rate is needed. n^4 at n = 60 is 60 × 60 × 60 × 60 = 12,960,000, which is about 1.3 × 10^7 and fits the compiled budget. n^5 at n = 60 is about 7.8 × 10^8, which is over the budget, so n^4 is the largest that fits.

Exercise 3. The limit is n at most 3000, and your plan uses three nested loops, one for each of i, j and k. Does it fit? What is the largest limit for which it fits in the compiled budget?

Show the answer

The count is n^3. For n = 3000 that is 3000 × 3000 × 3000 = 2.7 × 10^10, which does not fit. The budget of 10^8 steps would allow n up to about 464, because the cube root of 10^8 is about 464. The table uses 400 to leave a margin for the loop body, and 400^3 is 6.4 × 10^7. A limit of 3000 needs a different approach.

Exercise 4. A problem with a per-test limit of n^2 steps has a budget of 10^8 steps for the compiled language and about 2 × 10^7 for Python. What is the largest n for each?

Show the answer

For the compiled budget, n^2 is at most 10^8, so n is at most 10^4. For the Python budget, n^2 is at most 2 × 10^7, so n is at most about 4,470, because the square root of 2 × 10^7 is about 4,472. The Python limit is much lower, which is why the same plan can pass in one language and fail in another.

Exercise 5. A file has up to 10^6 numbers, each between 1 and 10^9. You need to count how many different values appear. Which approach fits, and what is its step count?

Show the answer

A set made in one pass costs about one step per number, so about 10^6 steps, which fits easily. Sorting the numbers first costs about n log n, which is about 2 × 10^7 steps, and also fits. The set is the simpler choice here. The values only go up to 10^9, but the approach does not loop over the values, so that limit does not matter.

Summary

• A limit such as 10^5 or 10^6 is a hint about which growth rate is allowed.
• Write the step count of each candidate approach as a formula in n, then compare it with a budget you have measured on your own machine.
• A rough budget is about 10^8 steps a second for compiled code and about 2 × 10^7 for a Python loop with real work in it.
• A limit on values is not a limit on loops, and a limit on the total of several test cases applies to the worst single test.
• Check the approach by counting the work inside each loop, including lookups in lists, not only the loops themselves.