How Fast Is It?
GOALCount how much work a program does, and read the limits to choose an approach.
Two programs can give the same answer, one in a second and one in an hour. What matters is not how many lines you wrote but how many times the computer repeats something. The limits in a problem tell you which approach will fit.
ON THIS PAGE
//THE EXAMPLE
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v = {4, 8, 15, 16, 23, 42};
int n = v.size();
long long steps = 0;
for (int i = 0; i < n; i++) {
steps++;
}
cout << "one loop: " << steps << endl;
steps = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
steps++;
}
}
cout << "two loops: " << steps << endl;
return 0;
}one loop: 6 two loops: 36
//LINE BY LINE
Watch it run
An array of 6. One loop looks at each cell exactly once.
Choosing from the limits
The limits in a problem are not arbitrary — they are telling you which approach will fit. Read them BEFORE you write any code.
| n at most | What fits |
|---|---|
| 10 | Бүх сэлгэмж, ухран буцах / Anything, even all permutations |
| 1 000 | O(n²) — хоёр давхар давталт / a double loop |
| 100 000 | O(n log n) — эрэмбэлэлт, хоёртын хайлт / sorting, binary search |
| 1 000 000 | O(n) — нэг л удаа явах / a single pass |
Reckon on about 100 million simple operations a second. Python is 10 to 50 times slower, so an approach that fits in C++ may not fit in Python.
What actually counts
Constants do not matter. O(2n) and O(n) count as the same, because as n grows they grow at the same rate. What matters is the SHAPE of the growth.
- Two loops one after the other — O(n) + O(n) is still O(n).
- A loop inside a loop — O(n) × O(n) is O(n²).
- Halving the work each time — O(log n).
- Sorting — O(n log n).