Algorithm Complexity: How Fast Does a Program Run?

Lesson 1 of 4 · Algorithm complexity

Two 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.

Before you start: prerequisites – loops, arrays.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

Counting operations

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.

Big O notation

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.

ComplexityNameA typical example
O(1)constanta formula, accessing a[i]
O(log n)logarithmicbinary search, fast exponentiation
O(√n)square rootchecking whether a number is prime (divisors up to √n)
O(n)linearone pass through an array
O(n log n)"n log n"sorting
O(n²)quadratictwo nested loops, all pairs
O(n³)cubicthree loops, Floyd-Warshall
O(2ⁿ)exponentialall subsets, backtracking
O(n!)factorialall permutations

Estimating from the task constraints

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:

ConstraintThe slowest complexity that passes (≈1 s)What it usually means
n ≤ 10–11O(n!)all permutations
n ≤ 20–25O(2ⁿ)all subsets, backtracking
n ≤ 500O(n³)three loops, DP with three indexes
n ≤ 5,000O(n²)two loops, DP with two indexes
n ≤ 106O(n log n)sorting, binary search, priority_queue
n ≤ 108O(n)one pass, prefix sums
n ≤ 1018O(log n) or O(1)a formula, binary search on the answer, fast exponentiation
Example: "n ≤ 200,000 numbers are given; print how many pairs have the sum K". Two loops would be 2·1010 steps – too slow. O(n log n) is needed: sorting + two pointers or binary search.

How to determine the complexity of code

  • Consecutive parts are added, and the larger one dominates: O(n) + O(n²) = O(n²).
  • Nested loops are multiplied: a loop up to n inside a loop up to n is O(n²).
  • A loop in which the variable is divided or multiplied by 2 has O(log n) steps: while (n > 0) n /= 2;
  • A call of a library function has its own complexity: 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++;
}
A trap: 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 complexity

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.

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: easy

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

1

Output

1

Example 2

Input

8

Output

4

Example 3

Input

1000000000000000000

Output

60
TASK 02Difficulty: medium

Pairs with the sum K – fast

n ≤ 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.

Example 1

Input

6 10
1 9 3 7 5 2

Output

2

Example 2

Input

3 4
2 1 3

Output

1
Common mistakes and tips
  • Always look at the constraints in the task statement first – they reveal the expected complexity.
  • Keep a sum or a product of large numbers in a long long; complexity does not help if the result is wrong because of an overflow.
  • Library functions are not "free" – check their complexity.

Check your knowledge

Open the quiz

Algorithm complexity

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?