Skip to content

Complexity & Constraints

In one sentence

Before writing code, estimate how many steps your idea takes for the largest input. Compare that with about \(10^7\) simple Python steps per second, and the constraints will tell you which algorithm you need.

1. What problem does it solve?

Example — 1520D · Same Differences (1-Set · C, 4-Misc · J, rating 1200)

You are given an array \(a_1, \dots, a_n\). Count the pairs of indices \((i, j)\) with \(i < j\) and \(a_j - a_i = j - i\).

Limits: \(t \le 10^4\) test cases, \(n \le 2 \cdot 10^5\), the sum of \(n\) over all test cases \(\le 2 \cdot 10^5\).

Input          Output
4
6
3 5 1 4 6 6    1
3
1 2 3          3
4
1 3 3 4        3
6
1 6 3 4 5 6    10

Two correct ideas, with very different running times:

idea steps for \(n = 2 \cdot 10^5\) verdict
try every pair \(i < j\) and check the equation \(\frac{n(n-1)}{2} \approx 2 \cdot 10^{10}\) way too slow
rewrite the equation, then count with a dictionary \(n = 2 \cdot 10^5\) fast

The rewrite. Move \(i\) and \(j\) to the sides they belong to:

\[ a_j - a_i = j - i \iff a_j - j = a_i - i . \]

So define \(b_i = a_i - i\). A pair is good exactly when \(b_i = b_j\). Now we just count equal values, in one pass.

Both ideas give the right answer. Only the step count decides whether it passes, and you can know that before coding.

2. The math

2.1 Counting steps: Big-O

We count how the number of basic steps grows with the input size \(n\), and keep only the fastest-growing term, without constants:

  • \(3n + 5\) steps → \(O(n)\)
  • \(n^2 / 2 + 100n\) steps → \(O(n^2)\)
  • two loops one after the other, each \(O(n)\) → \(O(n)\)
  • a loop inside a loop, each \(O(n)\) → \(O(n^2)\)
  • halving a range until it is empty → \(O(\log n)\)

Why drop constants? For large \(n\) the shape dominates: at \(n = 10^5\), \(100n = 10^7\) while \(n^2 = 10^{10}\).

2.2 Growth table

\(n\) \(\log_2 n\) \(n\) \(n \log_2 n\) \(n^2\) \(2^n\)
10 3 10 33 100 1024
\(10^3\) 10 \(10^3\) \(10^4\) \(10^6\) —
\(10^5\) 17 \(10^5\) \(1.7 \cdot 10^6\) \(10^{10}\) —
\(2 \cdot 10^5\) 18 \(2 \cdot 10^5\) \(3.5 \cdot 10^6\) \(4 \cdot 10^{10}\) —
\(10^9\) 30 \(10^9\) — — —

2.3 From constraints to algorithm

CPython runs roughly \(10^7\) simple steps per second. PyPy is often \(5\)–\(10 \times\) faster. A typical limit is \(1\)–\(2\) seconds, so aim for at most about \(10^7\) steps in CPython.

largest \(n\) allowed typical algorithms
\(\le 10\) \(O(n!)\) try all permutations
\(\le 20\) \(O(2^n)\) try all subsets, backtracking
\(\le 500\) \(O(n^3)\) three nested loops, small DP
\(\le 5000\) \(O(n^2)\) two nested loops, LCS-style DP
\(\le 2 \cdot 10^5\) \(O(n \log n)\) sorting, binary search, heaps, Dijkstra
\(\le 10^6\) \(O(n)\) prefix sums, two pointers, BFS/DFS, counting with a dict
\(\ge 10^9\) \(O(\log n)\) or \(O(1)\) a formula, binary search on the answer

Read the constraints first. Same Differences says \(n \le 2 \cdot 10^5\): the table rules out \(O(n^2)\) before you write a line.

2.4 "The sum of \(n\) over all test cases"

With \(t = 10^4\) tests you might fear \(10^4 \cdot 2 \cdot 10^5\). But the statement caps the sum of all \(n\) at \(2 \cdot 10^5\). So an \(O(n)\) solution per test costs \(O(\sum n) = O(2 \cdot 10^5)\) in total. Many Codeforces problems have this line. Look for it.

2.5 What Python operations cost

operation cost note
a[i], a.append(x), a.pop() \(O(1)\)
a.pop(0), a.insert(0, x) \(O(n)\) use collections.deque
x in a for a list \(O(n)\) scans the list
x in s for a set / dict, d[x], d.get(x, 0) \(O(1)\) average
a.sort(), sorted(a) \(O(n \log n)\)
a[l:r] (slicing) \(O(r - l)\) it copies
sum(a), min(a), max(a), a.count(x) \(O(n)\) each call walks the list
s = s + c in a loop (strings) \(O(\text{len}(s))\) each time builds a new string, so \(O(n^2)\) overall
heapq.heappush / heappop \(O(\log n)\)

The classic hidden \(O(n^2)\): calling an \(O(n)\) operation (in on a list, sum, count, pop(0), slicing) inside a loop of \(n\) iterations. For example, a.count(b[i]) for every \(i\) in Same Differences is \(O(n^2)\) again.

2.6 Amortized cost

Sometimes one step is expensive, but all steps together are cheap. In the sliding window, the inner while can run many times in one iteration, but left moves at most \(n\) times in the whole program, so the total is \(O(n)\). Count the total movement, not the worst single iteration.

2.7 Memory

A typical limit is \(256\) MB. A Python list of \(10^6\) small ints uses about \(8\) MB for the list. A \(5000 \times 5000\) 2D list is \(2.5 \cdot 10^7\) entries, about \(200\) MB: too close. Also remember that deep recursion stores one call frame per level.

3. Worked solution — Same Differences

Walk left to right. cnt[b] is how many earlier indices had \(a_i - i = b\). Each of them forms a good pair with the current index.

import sys

input = sys.stdin.readline


def solve():
    n = int(input())
    a = list(map(int, input().split()))

    cnt = {}
    ans = 0
    for i in range(n):
        b = a[i] - i
        ans += cnt.get(b, 0)
        cnt[b] = cnt.get(b, 0) + 1

    print(ans)


t = int(input())
for _ in range(t):
    solve()

Using \(0\)-based \(i\) does not change anything, because only equality of \(b\) matters: shifting every \(b\) by \(1\) keeps equal values equal.

Trace on the fourth test, 1 6 3 4 5 6:

\(i\) \(a_i\) \(b = a_i - i\) earlier with the same \(b\) ans
0 1 1 0 0
1 6 5 0 0
2 3 1 1 1
3 4 1 2 3
4 5 1 3 6
5 6 1 4 10

Five indices share \(b = 1\), and \(\binom{5}{2} = 10\) pairs. ✓

Cost: one pass with \(O(1)\) dictionary operations: \(O(n)\) per test, \(O(\sum n)\) overall.

4. Simulation and brute force

When the constraints are small, the straightforward solution is the right one. Do exactly what the statement says (simulation), or try every possibility (brute force / enumeration). Just count the steps first:

situation direct approach steps OK?
1742C · Stripes: an \(8 \times 8\) grid check every row and column \(64\) yes
check all pairs \(i < j\), \(n \le 5000\) two loops \(1.25 \cdot 10^7\) borderline in CPython, fine in PyPy
check all pairs \(i < j\), \(n \le 2 \cdot 10^5\) (Same Differences) two loops \(2 \cdot 10^{10}\) no, needs the rewrite

5. Common mistakes

Ignoring the constraints

Coding the first idea without checking \(n\) is the most common reason for TLE. Estimate first, then code.

Hidden \(O(n)\) inside a loop

if x in my_list, my_list.pop(0), a.count(x), sum(a[:i]) inside a loop of \(n\) iterations is \(O(n^2)\). Use a set, a dict, a deque, or a prefix sum.

Allocating per test case with a fixed maximum size

With \(t = 10^4\) tests, cnt = [0] * 200001 inside solve() costs \(10^4 \cdot 2 \cdot 10^5\) even though \(\sum n\) is small. Size arrays by the current \(n\), or use a dict, as above.

Counting only the loop, not the work inside

A loop of \(n\) iterations that calls sorted() each time is \(O(n^2 \log n)\), not \(O(n)\).

6. Practice

Problem Set Rating Point
1520D · Same Differences 1 · C, 4-Misc · J 1200 this page
1742C · Stripes 4-Misc · I 900 tiny input: simulate
1619C · Wrong Addition 4-Misc · D 1200 simulate digit by digit
1520C · Not Adjacent Matrix 4-Misc · H 1000 \(n \le 100\): construct directly
1807D · Odd Queries 1 · A, 4-Misc · A 900 \(O(nq)\) is too slow, so use a prefix sum
Credits & licenses