Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 63 ยท Contest Toolkit

Estimating Time and Memory

Estimate runtime and memory before coding: operations per second, Python constant factors, timing with perf_counter, list versus array memory, and choosing approaches.

Big-O notation tells you how an algorithm grows; a contest tells you whether it finishes in, say, two seconds on a machine you cannot see. Bridging the two is a skill of estimation: turn the constraints into a count of operations, turn the count into seconds for your language, and decide on the approach before you write a line of code. A strong contestant rejects a hopeless idea in thirty seconds instead of coding it for ten minutes.

This lesson gives you rules of thumb for Python, shows how to measure real timings with time.perf_counter, compares the memory cost of different containers, and ends with a decision routine. If big-O is new, start with the Big-O lesson in the DSA tutorial; here we focus on numbers.

The operations budget

A compiled language such as C++ does about 10^8 to 10^9 simple operations per second. CPython manages roughly 10^6 to 10^7 bytecode-level operations per second in ordinary loops: a statement like total += a[i] costs far more than one machine instruction. So for a time limit of one to two seconds, a safe working budget is:

Style of code Rough budget per second
Plain Python loop bodies with a few operations 5 * 10^6 to 10^7 iterations
Built-ins running in C (sum, sorted, max, slicing, str.join) 10^8 elementary steps or more
NumPy vector operations 10^8 to 10^9 elements

Then compute: operations = (complexity formula at the maximum n) * (cost of one step). If n = 2 * 10^5 and you plan O(n log n) with a heap, that is about 2 * 10^5 * 18 = 3.6 * 10^6 heap steps. heapq is implemented in C, so that fits. An O(n^2) idea with the same n is 4 * 10^10 and is dead on arrival.

Two more points:

  • The estimate is for the worst test, not the sample. A multiple-test input bounded by "sum of n <= 2 * 10^5" lets you treat it as one big test.
  • Constants matter inside the same complexity class. A loop with a dictionary lookup, a function call and a tuple creation may be five times slower than a loop with plain arithmetic.

Python constant factors

Some operations are cheap and some are surprisingly expensive:

  • Function calls cost roughly as much as several additions. Calling a tiny helper ten million times is slow; inline it in hot loops.
  • Attribute lookups and global names (such as math.sqrt inside a loop) are slower than locals; bind them once: sqrt = math.sqrt.
  • List indexing is cheap; 2D indexing grid[i][j] costs two lookups.
  • Building tuples and small objects allocates memory every time.
  • Recursion is slower than loops (each call creates a frame) and is limited in depth.
  • Big integers grow slower as the numbers get larger; multiplying two 100,000-digit integers is not O(1).
  • Dictionary and set operations are O(1) on average, but with a bigger constant than list indexing.

The best general speedup is to move the loop into C: replace a Python loop with sum, max, sorted, a comprehension, str.count, or a built-in like itertools.accumulate.

Measuring with perf_counter

Guessing is good; measuring is better. time.perf_counter() returns a high-resolution clock suitable for timing short code. Time a function at a moderate size, double the size, and see how the time grows. The ratio tells you the complexity class in practice: about 2x means linear, about 4x means quadratic.

The absolute seconds depend on your computer and the browser, so the demo prints ratios and shows qualitative results, which are stable.

Python Doubling n reveals the complexity

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see a ratio near 2 for the linear function and near 4 for the quadratic one; the exact decimals vary with machine noise. Taking the minimum of a few repeats, as best_time does, removes most of that noise. On a real contest you rarely have time for this, but it is invaluable in practice sessions: if your solution takes 0.4 s at n = 5 * 10^4, a quadratic algorithm will need about 6.4 s at n = 2 * 10^5.

Extrapolating to the maximum

Use the measured time t at size n to predict the time at the maximum N:

  • Linear: t * N / n
  • O(n log n): t * (N log N) / (n log n)
  • Quadratic: t * (N / n)^2
Python Predicting the maximum-size runtime

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Starting from 0.05 s at 20,000 elements, a linear algorithm needs 0.5 s at 200,000, an n log n algorithm about 0.6 s, and a quadratic one 5 s. The same measurement therefore either approves or kills the idea depending on the complexity class.

Memory estimates

Typical memory limits are 256 MB. Python's containers are far heavier than the arrays of a compiled language, so estimate before you allocate.

  • A list stores 8 bytes per slot (a pointer on a 64-bit build). Small ints between -5 and 256 are shared; larger ints are separate objects of 28 or more bytes. A list of 10^6 distinct large ints can need around 36 MB or more.
  • A set or dict with 10^6 entries needs on the order of tens of megabytes to over a hundred, because of hash table overhead.
  • A tuple per record multiplies the cost. A million (x, y) tuples is much heavier than two lists of a million numbers.
  • A 2D list [[0] * m for _ in range(n)] with n = m = 5000 has 25 million slots: about 200 MB for pointers alone. Too big for most limits.
  • array.array('i', ...) stores 4 bytes per int, and bytearray stores 1 byte per value. They are the compact options in pure Python.
flowchart LR
    A["list of ints<br/>8 B pointer + int object"] --> B["array('i')<br/>4 B per item"]
    A --> C["bytearray<br/>1 B per item"]
    A --> D["set or dict<br/>hash table overhead"]

The same million numbers can cost from 1 MB (bytearray) to over 50 MB (a set), depending on the container.

Python Memory of lists versus arrays

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

sys.getsizeof on a list counts only its pointer table, not the int objects it points to, which is why the demo also adds a sampled estimate for the objects. The ordering is what you should remember: bytearray < array < list of pointers < list including int objects, and the table of a set is several times larger than the pointer table of a list holding the same numbers.

Precomputation: pay once, answer many times

Many problems give you one small set of data and then thousands of test cases or queries (T up to 10^5). If each query repeats the same work, the cost is T times that work. Precomputation means doing the shared work once before reading the queries, storing the results in a table, and answering each query by a lookup. The total changes from T * work to setup + T * lookup.

Four precomputations cover most contests:

  • Sieve. One pass over the numbers up to N marks the primes and records each number's smallest prime factor. After that, "is x prime?" is one lookup and factorizing x takes O(log x) steps. Setup costs about O(N log log N).
  • Factorials and inverse factorials modulo a prime. With two tables of length N, every binomial coefficient C(n, k) is three multiplications. The inverse table is built backwards from a single modular power (see modular arithmetic).
  • Prefix sums (and their 2D versions) turn "sum of a range" into one subtraction (see prefix sums). The same idea works for counts, XOR, minimum so far and "number of primes up to x".
  • Answer tables for a small domain. If x is at most 10^5 or 10^6 and there are many test cases, compute the answer for every possible x in one sweep (for example the divisor count of each number with a loop over multiples, O(N log N)) and print from the table.

Three rules keep precomputation safe:

  1. Build outside the test-case loop. Reading T, then rebuilding the sieve inside the loop, turns a fast solution into a time-out.
  2. Size the table from the constraints, not from the sample. The largest value in the statement is the table size (plus one for zero).
  3. Check the setup cost first. A table of 10^7 integers is fine in C++ but heavy in Python; if the setup alone is near the time limit, precomputation is not the right tool.
Python Sieve, binomial tables, prefix sums and answer tables

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Choose the approach before coding

Combine all of this into a routine of about a minute:

  1. Write the maximum sizes from the statement.
  2. Propose the simplest idea and compute its worst-case operation count.
  3. If it is over your budget (about 10^7 plain Python steps), look for the structure that removes a factor of n: sorting, hashing, prefix sums, two pointers, binary search, a heap.
  4. Estimate memory of the data you will build.
  5. Only then code, and keep the cheap brute force handy for stress testing.
flowchart TD
    A["Read limits"] --> B["Estimate ops of simplest idea"]
    B --> C{"Within budget?"}
    C -->|"Yes"| D["Check memory, then code"]
    C -->|"No"| E["Find a faster structure<br/>or a better algorithm"]
    E --> B

Spend the first minutes on the estimate: a wrong plan costs far more than a slow start.

When two plans both fit, pick the one that is simpler to write and to get right. A slightly slower algorithm that you can code correctly in five minutes beats an elegant one that takes thirty.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. n = 200,000 and the time limit is 2 seconds. Which plain Python approach is realistic?

    O(n log n) is a few million steps, fine for Python. The others need 10^10 or more steps.
  2. 2. You measured 0.2 s for a quadratic solution at n = 10,000. About how long does n = 40,000 take?

    Quadratic time scales with the square of n. A 4x larger n means 16x the time: 0.2 * 16 = 3.2 s.
  3. 3. Which container is the most compact for one million small non-negative integers below 256?

    A bytearray uses one byte per item. A list needs an 8-byte pointer per slot, and sets and dicts add hash table overhead.
  4. 4. Why do you take the minimum of several timing repeats?

    Interruptions and other load can slow a run but never speed it up, so the fastest repeat is the cleanest measurement.

Summary

  • Turn constraints into an operation count for the worst test, then compare it with a budget: roughly 5 * 10^6 to 10^7 plain Python iterations per second.
  • Built-ins and NumPy move loops into C and can handle far more elements.
  • Function calls, tuple creation, global lookups and recursion add constant factors.
  • Measure with time.perf_counter, double the size and watch the ratio: about 2 means linear, about 4 means quadratic; use the minimum of repeats.
  • Python containers are heavy: use array or bytearray for big numeric tables, and avoid huge 2D lists and tuple-per-item designs.
  • Decide on the approach before coding: estimate time and memory, and choose the simplest plan that fits.

Next: Stress Testing with a Brute Force