Basics 0/97

Lesson 2 of 8

Time complexity

Describe how an algorithm’s work grows, count its operations, and use input limits to compare approaches.

5,827 words · 26 min read

Part 1 of 10 A program that is too slow

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 nn integers. Print how many different values the list contains.

The first input line holds nn, and the second line holds the nn integers x1,x2,…,xnx_1, x_2, \dots, x_n.

Constraints

  • 1≤n≤2⋅1051 \le n \le 2 \cdot 10^5
  • 1≤xi≤1091 \le x_i \le 10^9
  • 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

Sign up to run
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.