Time limits and a first program
A judge, the site that runs your program on its tests, stops any program that runs past the time limit, which is one second for the problem below. An interviewer asks the same thing out loud: what happens to your solution when the list has a million values? You can answer before running anything, by counting how many turns the loops of the program make. Here is a problem where a natural first program passes the sample and fails the judge.
You get a list of integers. Print how many different values the list contains.
The first input line holds , and the second line holds the integers .
Constraints
- Time limit: 1 second
Sample · Input
5 2 3 2 2 3
Output
2
The sample is this list of five values:
Only the values 2 and 3 appear in it, so the answer is 2. A direct way to count is to keep a list of the values seen so far and to add each value that is not in it yet. At the end, the length of that list is the answer.
Distinct Numbers with a list of seen values
def count_distinct(nums):
seen = []
for x in nums:
if x not in seen:
seen.append(x)
return len(seen)
print(count_distinct([2, 3, 2, 2, 3]))The function returns 2 for the sample. We then gave it the largest input the problem allows, 200,000 values that are all different. On our laptop it ran for about two minutes, against a limit of one second.
Five values are too few for any method to be slow, so the sample could not have warned us. We need a way to tell from the code how the work grows as the list gets longer. A program's time complexity describes that growth: roughly, how many simple steps the program takes for an input of a given size. With it we can tell from the code whether a program is fast enough without running it, and even check an idea before we write any code.
Count the operations of a program
An operation is one simple step: adding or comparing two numbers, or reading or writing one variable or one position of a list. A computer takes about the same tiny amount of time for each, so the number of operations stands in for the running time.
Let be the number of values in the list. The loop in count_distinct makes one turn for each value, turns in all. If every turn took a fixed number of operations, 200,000 values would be finished at once.
But x not in seen is not one operation. Python compares x with the stored values one at a time, until one of them is equal or the list ends. The line is a loop of its own, inside the loop we wrote.
We do not have to count every operation. Each comparison comes with the same few other steps, such as moving on to the next stored value, so the running time is about a fixed multiple of the number of comparisons, and we count only those. Their number depends on the input. It is largest when all the values are different: every value is then added to seen, so each new value is compared with every value before it.
Count the turns of the inner loop
To count the work of a loop inside a loop, we add up the turns of the inner loop over every turn of the outer one. Take five values that are all different, and compare each value with every value before it. The value at position 0 has nothing before it. The value at position 1 is compared with one earlier value, the value at position 2 with two, and so on up to position 4, whose value is compared with four. That makes comparisons, one for each pair of positions.
For different values the pattern is the same: the value at position is compared with the values before it. Adding these up gives the total number of comparisons:
With this is , the ten cells of the figure. With , the largest list in Distinct Numbers, it is , about twenty billion comparisons.
A rule of thumb turns such a count into time: a judge runs roughly simple operations a second. Twenty billion is 200 times that, so the estimate is around 200 seconds where the limit is one. The two minutes we measured are in line with it, because x not in seen makes its comparisons inside the interpreter, in fast C code.
The worst case
We counted a list of different values because that is the input on which the program is slowest. If all 200,000 values were equal, seen would never hold more than one value, and the program would make 199,999 comparisons and finish at once. A judge's tests can include the slowest inputs, and so can the data a program meets in real use. So the count that matters is the largest one among all inputs of the same size, which is called the worst case. A time complexity describes the worst case unless it says otherwise.
Big O notation
Big O notation describes how fast the number of operations grows as the input gets larger. Comparing every pair among values takes comparisons, and in Big O this count is written , read "order squared". We kept the term that grows fastest, , and dropped the constant in front of it.
The term can be dropped because it stops mattering as grows. At the two terms are
and leaving out the smaller one changes the count by one part in 200,000.
Growth when the input doubles
The constant in front can be dropped because it does not change how the count reacts when the input grows. When doubles, a count proportional to doubles and a count proportional to is multiplied by four, whatever the constant is:
So an program that takes one second on 10,000 values takes about four seconds on 20,000 and about 100 seconds on 100,000. The constant depends on the machine, the language and what we chose to count as one operation. The growth depends only on the algorithm. A faster computer makes every step quicker by the same factor, so on a judge, on our laptop or on a phone, this program takes four times as long when doubles.
Our slow program behaves this way. It took 0.26 seconds on 10,000 different values, 1.1 seconds on 20,000 and 4.6 seconds on 40,000, four times as long each time the input doubled.
More counts in Big O
The same two steps, keeping the fastest-growing term and dropping its constant, turn any count into Big O:
- is , called linear time.
- is , called quadratic time.
- is also . Once passes 1,000 the squared term is the larger one, and it keeps pulling ahead.
- A count that does not depend on , such as 7, is , called constant time.
Deeper read: the formal definition of Big O
"Keep the fastest-growing term" is a rule of thumb for the following definition. A count is when there are constants and such that
In words, from some input size onward, a fixed multiple of stays above the count. For the constants and work, because once we have and :
The definition is an upper bound, so is also . That is true but says less, and by convention a quoted complexity is the smallest simple bound that holds. , read "omega", is the matching lower bound: from some size onward the count is at least a fixed multiple of . , read "theta", says that the count is both and .
Read the complexity from the code
For Big O you do not need the exact count: a few rules give the complexity from the shape of the loops. In the examples, and are sizes of the input.
One loop
A loop costs the number of turns it makes times the work of one turn. This loop makes turns and does a constant amount of work in each, so it is :
total = 0
for x in nums:
total += xA loop that makes turns, or , or one that visits every second value, is as well, because constants and smaller terms drop out. Code that makes no loop over the input, such as reading nums[0] or adding two numbers, is .
A loop inside a loop
When one loop is inside another, the inner loop runs in full on every turn of the outer one, so the numbers of turns multiply. The assignment below runs times, which is :
for i in range(n):
for j in range(m):
grid[i][j] = 0Both sizes stay in the answer, because either of them can be the large one. When both loops run over the same values, the result is .
The inner loop of our slow program does not have the same length on every turn. For Big O we can treat every turn as if it were the longest one: at most comparisons on each of turns is at most comparisons, which is , the same answer the exact count gives. A bound like this never undercounts. For some programs it overcounts by a wide margin, and then we add up the turns exactly, as we did for the slow program.
Loops one after another
When parts of a program run one after another, their counts add, and Big O keeps the largest. This code makes turns and then more, so it is :
for i in range(n):
for j in range(n):
count += 1
for i in range(n):
count += 1With two different sizes neither part can be dropped. If the last loop ran over other values instead, the code would be .
Operations that hide a loop
These rules count loops, and some loops are not written with for or while. A built-in operation can be a loop inside, as x not in seen was. Here are the costs of some common operations, where a is a list of values:
Deeper read: the cost of a recursive function
To find the cost of a recursive function, add up, over all its calls, the work each call does apart from the calls it makes. When every call does a constant amount of its own work, the total is the number of calls times a constant. A function that calls itself once with , until reaches 1, makes calls, so it is .
A function that calls itself twice with makes many more:
def g(n):
if n == 1:
return
g(n - 1)
g(n - 1)The call g(n) makes two calls of g(n - 1), which make four calls of g(n - 2), and so on down to calls of g(1):
With constant work in each call that is : about a million calls for and about a billion for .
Common complexity classes
Programs with the same complexity form a complexity class, and a few classes cover almost every program in this course. The table lists them from the slowest-growing to the fastest, with the kind of code each one comes from and the value of its formula at three sizes.
| Class | Typical code | |||
|---|---|---|---|---|
| , constant | A formula, one position of a list | 1 | 1 | 1 |
| , logarithmic | Halving the input on every turn | 3 | 10 | 18 |
| Trying the divisors of a number up to | 3 | 32 | 447 | |
| , linear | One pass over the input | 10 | 1,000 | 200,000 |
| Sorting | 33 | 9,966 | 3,521,928 | |
| , quadratic | Every pair | 100 | 1,000,000 | 40,000,000,000 |
| , cubic | Every triple | 1,000 | 1,000,000,000 | |
| , exponential | Every subset | 1,024 | a 302-digit number | a 60,206-digit number |
| , factorial | Every ordering | 3,628,800 | a 2,568-digit number | a 973,351-digit number |
The numbers are the formulas with a constant of 1. A real program's count is some constant times that, so the columns give orders of magnitude and nothing finer.
The last two rows count choices. Each of items is either in a subset or out of it, which gives subsets, and items can be put in orders. A program that tries every subset or every order is usable only for very small .
Logarithms and halving
The logarithm in the second row counts halvings: is the number of times can be halved before it reaches 1.
Doubling adds one more halving, so a logarithm stays small: about 20 for a million and about 30 for a billion. An program therefore takes almost no time at any input size, and an program costs a small multiple of an one. Big O does not write the base of the logarithm, because changing the base only multiplies the count by a constant.
Binary search finds a value in a sorted list in time by halving the part of the list that can still hold it. Sorting gets its from halving too. Merge sort splits the list into two halves, then each half into two, until every piece holds one value, which takes about levels of splitting. Merging the pieces back together costs at each level, so the whole sort is .
Compare the growth of three classes
The graph plots , and for up to 32. Even over this short range the three curves pull apart. From to :
Below the graph, set an input size and a language. Each bar is one class at that size, and the dashed line marks the operations that fit in one second: about in C++ and about for a loop written in Python, for a reason the next part gives. Try and then .
From the input limits to a complexity
Once we know a program's complexity, the estimate we made for the slow program is quick. Take the largest the statement allows, work out the formula of the complexity for it, and compare the result with about operations for each second of the time limit. In Distinct Numbers goes up to 200,000:
An program is hundreds of times over the limit, and an program needs a few hundredths of the second.
It also works in the other direction. Given the largest input a problem allows, we can tell which complexities can pass, and so what kind of solution to look for. Each row of the table gives the fastest-growing complexity that still fits, and every slower-growing one fits as well:
| Largest | Complexity that still fits | Operations at that size | What it allows |
|---|---|---|---|
| Try every ordering | |||
| Try every subset and look at its items | |||
| Three nested loops | |||
| Every pair | |||
| Sort, then pass over the sorted values | |||
| A few passes over the input | |||
| A number in the input | or | about 60 halvings | A formula, or halving the value |
Adapted from USACO Guide: Time Complexity(opens in a new tab) ↗
These bounds are cautious, more so than the two tables they are adapted from. The USACO Guide's goes up to for and for , and the Competitive Programmer's Handbook's up to for . A short loop in C++ gets away with more than our table allows.
The table assumes operations a second. For a solution whose loops are written in Python, read it with a tenth of that: up to about and up to about 200.
The last row is for a single large number in the input, such as an exponent. A loop up to could make turns, so the program has to use a formula or halve again and again, about 60 times.
A small limit tells you less about the intended solution than a large one. Many easy problems have and are solved by a single pass. A small allows a slow program without asking for one, so write the simplest program that is correct.
Constant factors
Big O leaves out the number in front of the count, which is called the constant factor. Two programs with the same complexity can differ several times over in running time because of it: a loop whose body takes ten operations runs about ten times as long as a loop of the same length whose body takes one. The budget of operations a second averages over cheap and costly operations, and it is a cautious average: the USACO Guide notes that a judge can get closer to when the operations are cheap.
The language is part of the constant factor. A loop written in Python is slow: adding up ten million numbers in a for loop took 0.4 seconds on our laptop, and a loop with more in its body manages about simple operations a second. So for a Python loop we budget about ten times less. Built-in operations such as x in a and sorted(a) are loops inside the interpreter, written in C, and run several times faster than a loop written in Python. That is how the slow program got through about comparisons a second.
So the estimate is a first check. An estimate near passes and one near fails in either language. When it lands near the budget the constant factor decides, and the way to find out is to time the program on a large input that you generate yourself.
Only timing tells which of two programs with the same complexity is faster, and the answer can differ from one machine to another. Of two different complexities, the one that grows more slowly is faster once is large enough, whatever the constants. A program that takes steps is slower than one that takes up to about , and faster from there on.
Worked example
Find the fastest-growing class that fits
The trace makes this check one class at a time, from to , against a budget of operations, and keeps the last class that fits. It starts with . The other three inputs are 20, 400 and 200,000, and each ends on a different class.
n = 5,000 and the budget is 100,000,000 operations. Work out each class's operation count, slowest-growing first.
- n
- 5,000
- budget
- 100,000,000
Change the example input
Current result: "n^2"
Two faster programs for Distinct Numbers
By the table, calls for an program or a faster one. The slow part of our first program was the search through seen, so we need another way to tell whether a value has appeared before.
Sorting gives one. In a sorted list equal values are next to each other, so a value is new exactly when it differs from the value before it. On the sample:
Two cells of the sorted list start a new value, so the answer is 2.
Distinct Numbers by sorting
def count_distinct(nums):
values = sorted(nums)
count = 0
for i in range(len(values)):
if i == 0 or values[i] != values[i - 1]:
count += 1
return count
print(count_distinct([2, 3, 2, 2, 3]))The program has two parts that run one after the other, so its complexity is the larger of the two: for the sort and for the pass, which is in all. For 200,000 values that is about 3.5 million comparisons in the sort and 200,000 turns of the loop.
Distinct Numbers with a set
The other way keeps the first program and changes the container. A Python set finds a value by its hash instead of scanning, so adding a value takes time on average, and adding a value that is already in the set changes nothing. The Hashmaps lesson explains how a set does this.
def count_distinct(nums):
seen = set()
for x in nums:
seen.add(x)
return len(seen)
print(count_distinct([2, 3, 2, 2, 3]))The loop makes turns of work, so this version is on average. It is an average because on an unlucky input a hash lookup can take . The sorting version has no such input.
Running times of the three programs
Here is how long the three functions took on our laptop, on lists of different values:
| List of seen values | Sorting | Set | |
|---|---|---|---|
| 1,000 | 2.4 ms | 0.05 ms | 0.02 ms |
| 10,000 | 260 ms | 0.8 ms | 0.2 ms |
| 100,000 | 31 s | 13 ms | 3 ms |
| 200,000 | about 2 min | 40 ms | 10 ms |
At 1,000 values all three finish at once. Over the first three rows grows tenfold from one row to the next. The first column then grows about a hundredfold, as predicts, and the other two grow ten to twenty times.
Space complexity
Memory is counted the same way as time. A program's space complexity is the amount of memory it uses besides its input, as a function of and written in Big O. A fixed number of variables is space, a list or a set that can grow to values is , and a table of rows and columns is . When an interviewer asks for the complexity of a solution, give both the time and the space.
Time and space of the three programs
- List of seen values
time, space - Each membership test scans the list, which can grow to values.
- Sort, then compare neighbours
time, space - The sort costs more than the pass after it, and the sorted copy holds values.
- Set of seen values
time on average with a hash set, space - One insertion for each value. In a tree set such as C++
setan insertion is , which makes time.
Deeper read: checking a memory limit
To check a memory limit, multiply the number of stored values by the bytes each one takes. A C++ int takes 4 bytes on Linux, macOS and Windows. A table of of them and an array of of them take
CSES allows 512 MB for both problems in this lesson, so the table fits and the array is close to the limit. A Python list of numbers needs several times more memory for each value than a C++ array, because each slot holds a reference to a separate number object.
Practice: read the limits of a new problem
Here is a second problem. This time we read the limits first.
You get integers and a target . Find two different positions whose values add up to and print the two positions. Any valid pair is accepted. If no pair exists, print IMPOSSIBLE.
The first input line holds and , and the second line holds the values.
Constraints
- Time limit: 1 second
Sample · Input
4 8 2 7 5 1
Output
2 4
In the sample, positions 2 and 4 hold 7 and 1, and . The direct solution adds up every pair of positions, and we have counted pairs already: there are of them, which is sums for and about 200 seconds of work. The table asks for , and Distinct Numbers suggests where to find it: sort the values first, and then find the pair in one pass over the sorted list. Try to work out how that pass could go before you open the solution.
Solution: sort the values and move two markers inward
Sort the values, and put one marker on the smallest value and one on the largest. Add the two marked values and compare the sum with :
- If the sum equals , the two markers hold the answer.
- If the sum is too small, the value at the left marker cannot be in any answer, because even the largest value still in play is too small a partner for it. Move the left marker one step right.
- If the sum is too large, the value at the right marker cannot be in any answer, because even the smallest value still in play is too large a partner for it. Move the right marker one step left.
Sorting loses the original positions, which the problem asks for, so the program sorts each value together with its position, as (value, position), and prints the positions stored at the two markers.
def sum_of_two_values(nums, x):
pairs = sorted((value, i + 1) for i, value in enumerate(nums))
left, right = 0, len(pairs) - 1
while left < right:
total = pairs[left][0] + pairs[right][0]
if total == x:
return sorted([pairs[left][1], pairs[right][1]])
if total < x:
left += 1
else:
right -= 1
return None
data = sys.stdin.read().split()
n, x = int(data[0]), int(data[1])
nums = [int(v) for v in data[2:n + 2]]
answer = sum_of_two_values(nums, x)
if answer:
print(answer[0], answer[1])
else:
print("IMPOSSIBLE")On the sample the sorted list is (1, 4), (2, 1), (5, 3), (7, 2). The first sum, , is already 8, so the program prints the stored positions 4 and 2 in increasing order, as 2 4.
Each turn of the while loop either finds the answer or moves one marker one step toward the other, so the loop makes at most turns. With the sort, the program is : about 3.5 million comparisons and at most 199,999 marker moves, in place of twenty billion sums. The Two pointers lesson returns to this scan and shows why it never misses a pair.
Common complexity mistakes
Calling a loop over two different sizes .
- Where it breaks
- A grid of rows and columns takes visits. Calling the loop predicts and rules out a program that finishes at once.
- The fix
- Keep both sizes in the complexity, , and put the largest value of each into it.
Sorting inside a loop.
- Where it breaks
- A program that answers questions and sorts the same numbers again for each one pays for sorts. One sort is about operations, so the total is about .
- The fix
- Sort once, before the loop. The total is then one sort plus the work of the questions.
Removing values from the front of a list inside a loop.
- Where it breaks
- With 100,000 values, a loop that removes the first value on every turn (
a.pop(0)in Python,v.erase(v.begin())in C++) shifts 99,999 values, then 99,998, and so on: moves in all. - The fix
- Leave the list as it is and move an index forward.
Recall A problem allows $n \le 2{,}000$ and one second. Does an $O(n^2)$ program fit? An $O(n^3)$ one?
is far below , so a quadratic program fits easily. is 80 times , so a cubic program is far too slow.
Further reading
- USACO Guide, BronzeTime Complexity(opens in a new tab)
The module this lesson follows: Big O from loops, the common complexities, a table of limits, constant factors, the formal definition and a quiz.
- Antti Laaksonen (PDF)Competitive Programmer's Handbook, Chapter 2: Time complexity(opens in a new tab)
Pages 17 to 24 give the calculation rules, the complexity classes and a table of limits, then solve maximum subarray sum in , and and compare the measured running times.
- Jeff Erickson (PDF)Algorithms, Chapter 0: Introduction(opens in a new tab)
Section 0.6 measures running time by counting how often one chosen step runs, and shows with songs of linear and quadratic length why a faster singer or machine changes the constant but not the growth. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code.
- Pat MorinOpen Data Structures, Chapter 1: Introduction(opens in a new tab)
Section 1.3.3 writes out the exact cost of a two-line loop to show what Big O hides and compares with ; Section 1.5 sets worst-case, amortized and expected running times side by side. Parts of this page adapt this chapter’s text, licensed CC BY 2.5 Canada (creativecommons.org/licenses/by/2.5/ca), with changed wording, examples and code.
- Python documentationTime complexity of operations on built-in types(opens in a new tab)
The costs of list, dict, set and string operations in CPython, with notes on which costs are amortized and which are averages.
- OI Wiki, in Chinese复杂度简介 (Introduction to complexity)(opens in a new tab)
Formal definitions of , and , nested-loop and depth-first search examples, the master theorem for recurrences and space complexity.