Complexity analysis and deriving the target from N

A correct plan is not automatically a fast enough one. Every subtask carries a time limit, and a bound on N large enough to punish a slow plan even when that plan gives the right answer on every test. Complexity analysis is how you judge whether a plan will finish in time, from the bound alone, before you have written or run a single line of it.

Counting operations as N grows

Big-O describes how the number of operations a plan performs grows as N grows, ignoring constant factors and smaller terms. A single loop over N items performs about N operations: this is O(N). Two separate loops, each over N items, still add up to about 2N operations, which Big-O also calls O(N), since doubling a constant does not change the shape of the growth. A loop nested inside another loop, each running N times, performs about N * N operations: this is O(N^2).

N and N log N stay close together and grow gently. N^2 pulls far ahead of both once N passes a few hundred, and keeps pulling ahead faster the larger N gets. A plan whose operation count is O(N^2) can be fast enough for a small bound and still time out on a large one, even though the code never changes.

From a plan to a complexity

1n = int(input())2
3count = 04for i in range(n):5    for j in range(i + 1, n):6        count += 17
8print(count)

4

6

The outer loop runs n times. For each of those, the inner loop runs fewer times than the last, from close to n down to 0, but its length still grows in step with n. Dropping the constant factor that comes from that shrinking, the body still runs on the order of n * n times in total. That count is O(n^2). A plan with one loop over the input, doing a fixed amount of work per item, is O(n) instead. Sorting a list of n items is O(n log n), since a comparison-based sort compares roughly n log n pairs of items in the worst case, not the n^2 pairs a nested loop would check.

Reading a bound as a target complexity

A problem's bound on N tells you, roughly, which complexity a plan needs to have to finish in time. These figures are rules of thumb from how contest judges tend to be set up, not guarantees for any one problem:

Reading this table runs in the opposite direction from writing a plan. Once you have a bound, this table tells you roughly what complexity a working plan needs, before you have designed that plan. A bound of N ≤ 1000 allows an O(N^2) plan, since 1000^2 is one million, comfortably within what a judge can run in time. The same O(N^2) plan applied to a bound of N ≤ 10^6 would need about 10^{12} operations, far beyond what any judge finishes in time.

PyPy, which the grader runs, does roughly 10^7 to 10^8 simple operations per second. Plain CPython does roughly 10 to 50 times fewer. Both of these numbers are estimates, not exact figures, since the real cost also depends on what each operation does. Treat the table and these figures as a first estimate, not as proof. The module on testing already covers building a maximum-size test and timing it. That test is still the way to check a plan finishes in time, on the machine you have.

The cost of common built-ins

Some operations cost more than they look like they should, and knowing their rough cost helps you count operations accurately. Looking up a list by index, or a dictionary by key, costs O(1): roughly the same small amount of work no matter how large the list or dictionary is. Adding an item to the end of a list also costs O(1), on average. Checking whether a value appears anywhere in a list costs O(n), since it may need to check every item before it can be sure. The same check against a set or a dictionary's keys costs O(1) on average, since neither has to scan every item to answer. Sorting a list costs O(n log n).

Memory as a limit too

A judge also limits how much memory a program may use, commonly 512 megabytes. This rarely matters for small bounds, but it becomes real once N reaches the hundreds of millions. A list of N integers, on PyPy, costs roughly 8 bytes per integer, as a rule of thumb rather than an exact figure. A list of ten million integers costs roughly eighty megabytes: comfortably inside the limit. A list of a billion integers would cost roughly eight gigabytes: far past it. That is a sign a plan needs to avoid holding every value in memory at once, however fast its operations might be.

Recap

Big-O describes how a plan's operation count grows with N, ignoring constant factors. Examples include O(N) for one pass over the input, O(N log N) for a sort, and O(N^2) for a loop nested inside another loop. A problem's bound on N points, roughly, at which of these a working plan needs to reach, using the target-complexity table above. PyPy's rough operations-per-second budget and a rough memory-per-value figure turn a bound into an estimate, but both stay only estimates. A maximum-size test, run and timed on your own machine, is still what actually confirms it.