Time complexity

The time complexity of a program tells you how fast its number of steps grows as the input gets bigger. Make the input 10 times longer, and one program makes the same number of steps, another 10 times more, and a third 100 times more. Knowing it, you can tell whether an algorithm is fast enough for the input sizes you expect, before you write any code.

Explanation

A teacher has 6 students and wants to know how many of them were born in March. She asks each student one by one, so she needs 6 checks. In a class of 12, she would need 12 checks. The number of checks grows in proportion to the number of students $n$ , so this way of counting has linear time complexity, written $O (n)$ .

A row of 6 boxes with the months 3, 11, 3, 7, 11, 3; a blue frame moves from the first box to the last, and the three boxes with 3 turn dark blue as it reaches them.

Fig. 1. One box per student, with the month the student was born in.

To find the pairs of students born in the same month, compare each student with every student after them: student 1 with students 2 to 6, student 2 with students 3 to 6, and so on. For 6 students that is $5 + 4 + 3 + 2 + 1 = 15$ 5 + 4 + 3 + 2 + 1 = 15 checks, and 4 of them find a pair. For 12 students it is 66 checks. Twice the students take about four times the checks, because $n$ students make $n (n - 1) /2$ n(n - 1)/2 checks, which grows like $n^{2}$ n^2. This is quadratic complexity, $O (n^{2})$ O(n^2): a loop over the students with another loop over the students inside it.

Two curves of the number of checks against the class size n from 0 to 40: n, a straight line that stays low, and n(n - 1)/2, which bends upward and reaches 780 at n = 40.

Fig. 2. Checks against the class size: one per student for March, one per pair for the same month.

Counting how the steps grow gives one way to compare any two programs, whatever they compute. Once the input is large enough, the one whose count grows slower is faster: an $O (n)$ program beats an $O (n^{2})$ O(n^2) one.

A step is one simple operation, such as a comparison, an addition or reading a number. A program rarely makes exactly $n$ steps. The March count reads each month and compares it with 3, and it makes a few steps before and after the loop, so it takes something like $2 n + 5$ 2n + 5 steps. Such constants don't change how the count grows. At $n = 1 0^{6}$ n = 10^6, $2 n + 5$ 2n + 5 is still about twice $n$ , while $n^{2}$ n^2 is a million times $n$ . So only the part that grows fastest is kept, without its constant factor: $2 n + 5$ 2n + 5 is written $O (n)$ , and $n (n - 1) /2 = n^{2} /2 - n /2$ n(n - 1)/2 = n^2/2 - n/2 is written $O (n^{2})$ O(n^2) (read "big O of n squared"). The number of steps as a function of the input size, written this way, is the time complexity.

What is the time complexity of this code?

for (int i = 0; i < n; i++)
    for (int j = 0; j < 3; j++)
        s += a[i] * j;

$O (n^{2})$ O(n^2)

$O (n)$

$O (1)$

The difference matters for large inputs. For $1 0^{6}$ 10^6 students the pair program makes about $5 \cdot 1 0^{11}$ 5 \cdot 10^{11} checks. A common rule of thumb for turning steps into seconds is about $1 0^{8}$ 10^8 simple steps per second. It is a rough estimate, not an exact figure. At that speed the pair program takes about 5,000 seconds, well over an hour.

Once the complexity of the first approach is known, you can look for a faster one. Keep an array of 12 counters, one per month: counter 1 holds how many students were born in January, counter 12 how many in December. Go through the students once and add 1 to the counter of each student's month, then go through the 12 counters once. A month with $c$ students gives $c (c - 1) /2$ c(c - 1)/2 pairs, the same formula as before on a smaller group. That is $n + 12$ n + 12 steps, which is $O (n)$ .

To estimate a solution, go through four stages:

Find $n$ : the largest input size the statement allows.
Count the runs: how many times the busiest line runs on the worst input of that size, as a formula in $n$ . The busiest line is the one inside the most loops; each run of it counts as one step.
Keep the largest term: drop constant factors and smaller terms to get $O (\dots)$ .
Compare with the budget: the budget is the time limit in seconds times $1 0^{8}$ 10^8. Put the largest $n$ into the $O (\dots)$ form and compare. If the result is within a factor of about 3 of the budget, go back to the exact count with its constant.

For the pair program with up to $1 0^{6}$ 10^6 students and a time limit of 1 second: find $n$ : $1 0^{6}$ 10^6. Count the runs: $n (n - 1) /2$ n(n - 1)/2. Keep the largest term: $O (n^{2})$ O(n^2). Compare with the budget: $1 0^{12}$ 10^{12} against $1 0^{8}$ 10^8, far too slow. For the counting program, $O (n)$ gives $1 0^{6}$ 10^6 steps, a hundredth of the budget.

Estimate for the slowest input of that size, not a lucky one. A search for a student born in March can stop at the first student, or go through all $n$ students when nobody was born in March. Tests include inputs like that, so the search is $O (n)$ .

Common complexities

Fig. 3 shows how fast the number of steps grows for the complexities you meet most often. The constants are dropped, so only the shape of each curve matters.

Curves of the number of steps against n from 1 to 100 for 1, log n, square root of n, n, n log n, n squared and 2 to the n: 1 stays flat, log n and the square root of n rise slowly, n is a straight diagonal line, and n log n, n squared and 2 to the n shoot past the top before n reaches 25.

Fig. 3. Steps against the input size $n$ . Before $n$ reaches 25, the curves for $n lo g n$ n \log n, $n^{2}$ n^2 and $2^{n}$ 2^n are already past the top.

Complexity	Name	Twice the input	Typical code
$O (1)$	constant	the same steps	a formula, such as `n * (n + 1) / 2` for $1 + 2 + \dots + n$ 1 + 2 + \dots + n
$O (lo g n)$ O(\log n)	logarithmic	one more step	a loop that doubles `i`; binary search
$O (n)$ O(\sqrt n)	square root	about 1.4 times the steps	`for (long long d = 1; d * d <= n; d++)`, all divisors of `n`
$O (n)$	linear	twice the steps	one loop over the input
$O (n lo g n)$ O(n \log n)	$n lo g n$ n \log n	a bit more than twice	`sort`
$O (n^{2})$ O(n^2)	quadratic	four times the steps	a loop inside a loop, such as the pair loop
$O (n^{3})$ O(n^3)	cubic	eight times the steps	three loops, one inside the other
$O (2^{n})$ O(2^n)	exponential	the steps squared	all subsets of $n$ items
$O (n!)$	factorial	far more than squared	all orders of $n$ items, often with backtracking

$lo g_{2} n$ \log_2 n is how many times you can double 1 before passing $n$ : for (int i = 1; i < n; i *= 2) runs 20 times for $n = 1 0^{6}$ n = 10^6, because $2^{20} = 1, 048, 576$ 2^{20} = 1{,}048{,}576 is the first power of 2 above $1 0^{6}$ 10^6.

A complexity can depend on two input sizes. Take an array of $n$ numbers and an array of $m$ numbers. A loop over the first array, then a loop over the second, is $O (n + m)$ O(n + m): for $n = 1000$ n = 1000 and $m = 2000$ m = 2000 that is 3,000 steps. A loop over the second array inside a loop over the first, comparing every pair, is $O (n \cdot m)$ O(n \cdot m): 2,000,000 steps.

How many times does cnt++ run for $n = 6$ n = 6?

for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j += i)
        cnt++;

From the limits to the complexity

For a time limit of 1 second, with the rule of thumb of about $1 0^{8}$ 10^8 steps per second:

Largest $n$	Complexity that fits	Steps at that $n$
10	$O (n!)$	$10! = 3, 628, 800$ 10! = 3{,}628{,}800
20	$O (2^{n})$ O(2^n)	$2^{20} = 1, 048, 576$ 2^{20} = 1{,}048{,}576
400	$O (n^{3})$ O(n^3)	$6.4 \cdot 1 0^{7}$ 6.4 \cdot 10^7
5,000	$O (n^{2})$ O(n^2)	$2.5 \cdot 1 0^{7}$ 2.5 \cdot 10^7
$1 0^{6}$ 10^6	$O (n lo g n)$ O(n \log n)	about $2 \cdot 1 0^{7}$ 2 \cdot 10^7
$1 0^{8}$ 10^8	$O (n)$	$1 0^{8}$ 10^8, the whole budget: check the constant (stage 4)
$1 0^{12}$ 10^{12}	$O (n)$ O(\sqrt n)	$1 0^{6}$ 10^6
$1 0^{18}$ 10^{18}	$O (lo g n)$ O(\log n)	about 60

Find the largest $n$ in the statement and take the first row whose $n$ is at least that large. Aim for that complexity or a faster one.

A shop has up to 200,000 receipts. For each receipt, count how many receipts have a smaller total. The obvious program compares every receipt with every other one. Find $n$ : 200,000. Count the runs: each of the $n$ receipts is checked against $n - 1$ n - 1 others, so $n (n - 1)$ n(n - 1) checks.

When the constant matters

The constant matters in two cases: two solutions have the same $O (\dots)$ , or the estimate is within a factor of about 3 of the budget (stage 4). Then the kind of step matters: a division is slower than an addition. An inner loop over 26 letters for $n = 1 0^{7}$ n = 10^7 is $O (n)$ , but it is $2.6 \cdot 1 0^{8}$ 2.6 \cdot 10^8 steps, more than the budget of 1 second. Reading $1 0^{6}$ 10^6 numbers with cin also needs the line ios::sync_with_stdio(false); cin.tie(nullptr);.

Common mistakes

Missing a loop hidden in one line, such as s = s + c;, which copies the whole string each time, or v.erase(v.begin()), which moves all remaining elements one place forward. Write s += c;, and instead of erasing from the front keep an index that moves forward or use a queue.
Forgetting the cost of a built-in function. sort is $O (n lo g n)$ O(n \log n), not one step, so sorting inside a loop that runs $n$ times is $O (n^{2} lo g n)$ O(n^2 \log n); sort once, before the loop.
Forgetting the number of test cases, which multiplies the steps of one test by $t$ . Count $t$ times the steps for the largest $n$ , unless the statement limits the sum of $n$ over all tests.
Measuring the input by its length instead of its value, as if one input number made a program $O (1)$ , while checking every $d$ from 1 to $n$ is $O (n)$ . Stopping at $n$ \sqrt n makes it $O (n)$ O(\sqrt n).
Counting only the lucky case. Time limits are checked on the slowest input of each size, so a program that is fast on most inputs can still exceed the limit and lose points. Still, when you can't find a faster solution, a slow one is worth submitting: in contests that score each test, it earns the points of the small tests.

Was this page helpful?