Big O Notation : ce que les A-Level en informatique attendent réellement

La notation Big O apparaît dans tous les grands programmes d'informatique A-level (AQA, OCR, Edexcel) et elle pose problème à beaucoup d'étudiants, non pas parce que les maths sont difficiles, mais parce qu'ils ne la voient jamais liée à du code réel. Ceci est un guide pratique de ce que vous devez savoir et comment répondre aux questions d'examen sans détour.

Ce que Big O mesure réellement

Big O décrit comment le temps d'exécution (ou l'utilisation de la mémoire) d'un algorithme augmente quand la taille d'entrée, généralement appelée n, devient plus grande. Ce n'est pas une mesure au chronomètre en secondes. C'est une façon de décrire le taux de croissance pour pouvoir comparer les algorithmes indépendamment du matériel.

Quand vous écrivez O(n), vous dites : si je double l'entrée, le travail double à peu près. O(n²) signifie doubler l'entrée quadruple à peu près le travail. Cette relation est ce que les examinateurs veulent que vous identifiiez, pas des comptages d'opérations exacts.

Les complexités que vous devez maîtriser

Pour l'A-level, ce sont celles qui reviennent encore et encore :

• O(1) – temps constant. Accéder à un élément d'un tableau par index : arr[5]. Peu importe la taille du tableau.
• O(log n) – logarithmique. Recherche binaire sur une liste triée. Chaque étape réduit de moitié l'espace de recherche restant.
• O(n) – linéaire. Une seule boucle sur une liste, comme une recherche linéaire qui vérifie chaque élément une fois.
• O(n log n) – linéarithmique. Merge sort et quicksort (cas moyen) se situent ici.
• O(n²) – quadratique. Boucles imbriquées sur les mêmes données, ce que font exactement bubble sort, insertion sort et selection sort.
• O(2ⁿ) – exponentielle. Fibonacci récursif naïf sans mémorisation. Ça devient rapidement problématique.

Vous devez être capable de regarder du pseudocode et dire lequel c'est au premier coup d'œil, parce que c'est surtout ce qui est testé.

Lire le code pour trouver sa complexité

La méthode qui marche toujours : comptez les boucles et voyez comment elles se rapportent à n.

# O(n) - une boucle, un passage
for i in range(n):
    print(i)

# O(n^2) - boucle imbriquée, les deux liées à n
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - l'espace de recherche se divise par deux à chaque itération
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

Une boucle imbriquée où la plage de la boucle intérieure dépend de n est toujours O(n²), même si elle semble légèrement différente (comme for j in range(i) au lieu de for j in range(n) — c'est toujours quadratique en général, juste avec une différence de facteur constant).

Faites attention aux boucles qui ne dépendent pas du tout de n. Une boucle qui s'exécute toujours 10 fois indépendamment de la taille d'entrée est O(1), même s'il y a une boucle présente. Les examinateurs aiment glisser cela.

Algorithmes de tri courants et leur Big O

C'est un sujet d'examen préféré parce qu'il combine deux spécifications à la fois : les algorithmes de tri et la complexité.

Algorithme	Meilleur cas	Pire cas
Bubble sort	O(n)	O(n²)
Insertion sort	O(n)	O(n²)
Merge sort	O(n log n)	O(n log n)
Binary search	O(1)	O(log n)
Linear search	O(1)	O(n)

La cohérence de merge sort (même complexité meilleur et pire cas) vaut la peine d'être mentionnée explicitement si une question demande pourquoi vous le choisiriez plutôt que bubble sort pour de grands ensembles de données. Le meilleur cas de O(n) de bubble sort s'applique seulement avec une optimisation de sortie anticipée quand aucun échange n'a lieu dans un passage — mentionnez ce détail si vous l'évoquez, puisque certains organismes d'examen l'attendent.

Où les étudiants perdent des points

Le plus gros : écrire