Complexity and Big O Notation

First lesson of the Data Structures and Complexity course, free to read: about 20 minutes, 3 exercises and 3 quiz questions. This is the catalogue's base lesson; in the student space, it is rewritten for your profile.

Objectives

Estimate the number of operations an algorithm performs as a function of input size
Use Big O notation to compare algorithms
Measure execution time with timeit

Time complexity Big O notation Space complexity

Two programs can produce the same result and yet behave very differently: one answers in the blink of an eye on a million rows, the other runs for hours. Complexity lets you predict this behavior before you run the code.

Counting operations

We don’t measure seconds (which depend on the machine) but the number of elementary operations as a function of the input size n.

def contient(liste, cible):
    for x in liste:          # at worst n iterations
        if x == cible:       # 1 comparison per iteration
            return True
    return False

In the worst case (element absent), we make n comparisons: the cost is proportional to n.

def a_des_doublons(liste):
    n = len(liste)
    for i in range(n):              # n iterations
        for j in range(i + 1, n):   # up to n - 1 iterations
            if liste[i] == liste[j]:
                return True
    return False

Here, we compare every pair: about n²/2 comparisons. Doubling the size of the list quadruples the time.

Big O notation

O notation describes the order of magnitude of growth by keeping the dominant term and ignoring constants:

3n + 5 becomes O(n);
n²/2 + n becomes O(n²);
10 operations regardless of n: O(1) (constant time).

Why ignore constants? Because for large values of n, it is the shape of the curve that wins out: an O(n) algorithm always ends up beating an O(n²) one.

The classes to know

Complexity	Name	Example	n = 1,000,000
O(1)	constant	`liste[i]` access, dictionary key	1
O(log n)	logarithmic	binary search	about 20
O(n)	linear	iterating over a list	10⁶
O(n log n)	linearithmic	sorting with `sorted`	about 2 × 10⁷
O(n²)	quadratic	comparing all pairs	10¹²
O(2ⁿ)	exponential	testing all subsets	unthinkable

At one hundred million simple operations per second (an order of magnitude for Python), 10¹² operations take several hours.

Practical rules

Statements in sequence: you add them and keep the largest term (O(n) + O(n²) = O(n²)).
Nested loops: you multiply (O(n) × O(n) = O(n²)).
Dividing the problem in half at each step: O(log n).
Watch out for hidden operations: x in liste is O(n), so a loop that does if x in liste is O(n²).

What about memory?

Space complexity measures the extra memory used. Creating a copy of the list costs O(n) in memory; keeping two variables costs O(1). We often trade memory for time, as we will see with dictionaries.

Checking by measurement

import timeit
donnees = list(range(10_000))
t = timeit.timeit(lambda: contient(donnees, -1), number=100)
print(f"{t:.3f} s for 100 searches")

By doubling the size and observing the time, you confirm the analysis: time doubles for O(n), quadruples for O(n²).

Exercises

Solutions and tests stay on the server. In the student space, your code is run and checked, and the tutor gives hints before the solution.

Multiple choiceDifficulty 11 hint

Identify a complexity

What is the complexity of this function?

def somme_paires(l):
    total = 0
    for a in l:
        for b in l:
            total += a * b
    return total

O(n)
O(n²)
O(log n)
O(1)

CodeDifficulty 2Python in the browser1 hint

From O(n²) to O(n)

The function somme_paires(l) above computes the sum of a * b over all pairs (a, b), including a == b. Rewrite it in O(n) by noticing that this sum equals (sum of the elements)².

def somme_paires(l):
    pass

CodeDifficulty 2Python in the browser2 hints

Count the operations

Write nb_comparaisons(n) that returns the exact number of liste[i] == liste[j] comparisons performed by a_des_doublons (the two-loop version from the lesson) on a list of size n with no duplicates.

def nb_comparaisons(n):
    pass