How many times does it run?
For a given number n (1 ≤ n ≤ 1018) print how many times the body of the loop for (i = 1; i <= n; i *= 2) runs.
Example 1
Input
1Output
1Example 2
Input
8Output
4Example 3
Input
1000000000000000000Output
60Two correct programs can run for completely different times: one for a fraction of a second, and the other for hours. Complexity describes how the running time grows when the input grows. When we know it, we can estimate before writing the program whether the solution will fit in the time limit of the task.
We do not measure seconds (they depend on the computer), but the number of basic steps depending on the input size n. Let us look at three ways to calculate the sum 1 + 2 + … + n:
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
// 1) one loop: n additions – O(n)
long long s1 = 0;
for (long long i = 1; i <= n; i++) s1 += i;
// 2) two loops: we add 1 at a time – about n²/2 additions – O(n²)
long long s2 = 0;
for (long long i = 1; i <= n; i++)
for (long long j = 1; j <= i; j++) s2++;
// 3) a formula: three operations regardless of n – O(1)
long long s3 = n * (n + 1) / 2;
cout << s1 << " " << s2 << " " << s3 << endl;
return 0;
}
For n = 109 the first way runs for about a second, the second one would take centuries, and the third one is instant.
We say that an algorithm has the complexity O(f(n)) if the number of steps is at most proportional to f(n). Constants and smaller terms are ignored: 3n² + 5n + 7 steps is O(n²), because n² dominates for a large n.
| Complexity | Name | A typical example |
|---|---|---|
| O(1) | constant | a formula, accessing a[i] |
| O(log n) | logarithmic | binary search, fast exponentiation |
| O(√n) | square root | checking whether a number is prime (divisors up to √n) |
| O(n) | linear | one pass through an array |
| O(n log n) | "n log n" | sorting |
| O(n²) | quadratic | two nested loops, all pairs |
| O(n³) | cubic | three loops, Floyd-Warshall |
| O(2ⁿ) | exponential | all subsets, backtracking |
| O(n!) | factorial | all permutations |
A computer does about 108 simple operations per second. That is why the constraint on n in the task statement almost always shows what kind of solution is expected:
| Constraint | The slowest complexity that passes (≈1 s) | What it usually means |
|---|---|---|
| n ≤ 10–11 | O(n!) | all permutations |
| n ≤ 20–25 | O(2ⁿ) | all subsets, backtracking |
| n ≤ 500 | O(n³) | three loops, DP with three indexes |
| n ≤ 5,000 | O(n²) | two loops, DP with two indexes |
| n ≤ 106 | O(n log n) | sorting, binary search, priority_queue |
| n ≤ 108 | O(n) | one pass, prefix sums |
| n ≤ 1018 | O(log n) or O(1) | a formula, binary search on the answer, fast exponentiation |
while (n > 0) n /= 2;sort is O(n log n), s.insert into a set O(log n), v.erase(v.begin()) on a vector O(n)!// how many digits does the number n have in binary? – O(log n)
int bits = 0;
while (n > 0) {
n /= 2;
bits++;
}
for (int i = 0; i < s.size(); i++) s = s + "x"; looks like one loop, but every string concatenation copies the whole string – O(n²) in total. The same holds for v.insert(v.begin(), x) and erasing from the beginning of a vector.Memory is limited too (usually 64–256 MB). An array of 107 numbers of type int takes 40 MB, and of type long long 80 MB. The matrix int a[10000][10000] takes 400 MB – too much. That is why we also take care of the memory complexity: O(n) memory is almost always fine, and O(n²) only for n up to a few thousand.
Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.
For a given number n (1 ≤ n ≤ 1018) print how many times the body of the loop for (i = 1; i <= n; i *= 2) runs.
1184100000000000000000060n ≤ 2·105 different integers and a number K are given. Print how many (unordered) pairs have the sum exactly K. An O(n²) solution is too slow.
6 10
1 9 3 7 5 223 4
2 1 31long long; complexity does not help if the result is wrong because of an overflow.1. What is the complexity of two nested loops up to n?
2. The constraint is n ≤ 10⁶. Which complexity surely passes in about a second?
3. What is the complexity of the loop while (n > 0) n /= 2;?
4. About how many operations does a computer do per second?