Time Complexity in Competitive Programming: The 10^8 Rule
Turn a problem's constraints into the complexity that passes a 1-second limit at about 10^8 operations, and start every C++ solution from a fast-I/O template.
- Course: Competitive Programming study plan
- Module: Fast I/O and complexity budgets
- Kind: Lesson
- Reading time: 15 min
- Runtime: Clang 18 · C++20
How do I know which time complexity will pass in competitive programming?
Put the largest n from the constraints into each idea's complexity and compare it with about 10^8 simple operations per second of time limit. Under the line it passes. So n ≤ 10^6 allows O(n log n), n ≤ 10^4 allows O(n²), n ≤ 400 allows O(n³) and n ≤ 25 allows O(2ⁿ).
Lesson
A contest problem is judged twice: is the answer right, and did it arrive within the time limit? This lesson settles the second question before you write a line.
The template
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> a(n);
for (auto& x : a) cin >> x;
// solve
cout << answer << '\n';
}bits/stdc++.hincludes the whole standard library at once (GCC's libstdc++, which judges use). Fine for a contest, never in a project.using namespace stdsaves typing in a one-file solution.- The two fast-I/O lines make
cin/coutfast enough for 10⁶ numbers. After them, never mix inscanf/printf. ll— long long by default. Anintstops at about 2.1 × 10⁹; a sum of 10⁵ values of 10⁹ is 10¹⁴.- Print
'\n', notendl:endlflushes on every line.
Read the constraints first
A judge runs roughly 10⁸ simple operations per second. Put the largest n into your idea's complexity:
- n ≤ 10⁵ and an O(n²) idea → 10¹⁰ operations, a hundred times over. Too slow.
- n ≤ 10⁵ and O(n log n) → about 1.7 × 10⁶. Passes easily.
So the constraint on n names the slowest algorithm the setter allows. Watch the bars move as n grows:
about 10⁸ simple operations per second- n = 11: even O(n!) is only 4.0×10⁷ operations, so anything up to O(n!) fits.
- n = 25: O(2ⁿ) is 3.4×10⁷ operations, under the 10⁸ line, while O(n!) would be > 10¹². The slowest class that fits is O(2ⁿ), so that is the budget.
- n = 400: O(n³) is 6.4×10⁷ operations, under the 10⁸ line, while O(2ⁿ) would be > 10¹². The slowest class that fits is O(n³), so that is the budget.
- n = 10⁴: O(n²) is 1.0×10⁸ operations, under the 10⁸ line, while O(n³) would be 1.0×10¹². The slowest class that fits is O(n²), so that is the budget.
- n = 10⁶: O(n log n) is 2.0×10⁷ operations, under the 10⁸ line, while O(n²) would be 1.0×10¹². The slowest class that fits is O(n log n), so that is the budget.
- Read it the other way in a contest: the constraint on n names the slowest algorithm allowed. n ≤ 10⁶ means O(n log n) or better; an O(n²) idea is over by a factor of ten thousand.
The table to keep in your head, every row computed at 10⁸:
- n ≤ 11 → O(n!) · n ≤ 25 → O(2ⁿ) · n ≤ 400 → O(n³)
- n ≤ 10⁴ → O(n²) · n ≤ 10⁶ → O(n log n) · n ≤ 10⁸ → O(n)
- n up to 10¹⁸ → O(log n) or a formula
Habits that save a verdict
- Read the constraints before the idea. They are a hint.
- Use the worst case, not the example: the hidden tests are at the limit.
- Two seconds doubles the budget; it does not turn O(n²) at n = 10⁵ into a pass.
1LL * a * b, nota * b, whenaandbareint.
More practice
- Two Sum — O(n²) is the trap, a hash map is O(n).
- Contains Duplicate — sort or hash.
- Maximum Subarray — O(n) after spotting O(n²).
- Sort an Array — O(n log n) or bust.
Common questions
How many operations per second does a judge run?
Roughly 10^8 simple operations — additions, comparisons, array reads in a tight loop. It is a rule of thumb, not a constant: divisions, cache misses and heavy STL containers are slower, plain loops can be faster. It is the right order of magnitude to budget with.
Why use long long in competitive programming?
An int holds about ±2.1 × 10^9, and contest sums, products and pair counts pass that routinely — 10^5 values of 10^9 add up to 10^14. Signed overflow is undefined behaviour and usually a wrong answer, so values and totals go in long long, which holds about ±9.2 × 10^18.
What do ios::sync_with_stdio(false) and cin.tie(nullptr) do?
The first stops cin and cout synchronising with C's stdio, so they keep their own fast buffers; the second stops cout being flushed before every read. With large input they make reading and printing several times faster. Afterwards, do not mix scanf/printf with cin/cout.
What does n ≤ 10^5 tell me about the solution?
That O(n²), about 10^10 operations, is too slow, and the intended solution is O(n log n) or O(n) — sorting, binary search, prefix sums, two pointers or a hash map. The constraint is a hint the setter gives you on purpose.
Exercises
Sum and maximum, fast
Read n and then n integers. Print their sum and their maximum, separated by a space.
Constraints: 1 ≤ n ≤ 2·10⁵, -10⁹ ≤ aᵢ ≤ 10⁹.
Input: n on the first line, the values on the second. Output: <sum> <max>.
5
3 -1 4 1 5prints
12 5Pairs that add up to a multiple of k
Count the pairs (i, j) with 1 ≤ i < j ≤ n whose sum i + j is divisible by k.
Constraints: 1 ≤ n ≤ 10⁹, 1 ≤ k ≤ 10⁶. Time limit about one second.
Input: n k. Output: the number of pairs.
5 3prints
4(the pairs are 1+2, 1+5, 2+4 and 4+5.)
Read the constraints before you code: trying every pair is O(n²), and n reaches 10⁹.