Jour 17 Day 17 · vendredi 21 août 2026 Friday 21 August 2026 CS Fondamental

Complexité & Big O Complexity & Big O

La question tombe à chaque exercice de code : « quelle est la complexité ? ». Savoir y répondre — et repérer le O(n²) caché dans un innocent .includes() — change le verdict d'un entretien. The question comes after every coding exercise: "what's the complexity?". Knowing how to answer — and spotting the O(n²) hidden in an innocent .includes() — changes an interview's verdict.

L’essentiel

La notation Big O décrit comment le coût d’un algorithme (temps ou mémoire) grandit avec la taille de l’entrée n. Elle ne mesure pas des secondes : elle prédit le passage à l’échelle. Un algorithme rapide sur 100 éléments mais O(n²) explosera sur un million — et c’est exactement ce qu’un recruteur veut vérifier : est-ce que vous voyez venir l’explosion avant la prod ?

Big O garde le terme dominant et jette les constantes : 3n² + 50n + 1000 → O(n²). Pour de petits n, les constantes gagnent (un tri par insertion bat un merge sort sur 10 éléments) ; asymptotiquement, la classe de complexité gagne toujours.

L’échelle à connaître, avec un ordre de grandeur concret (≈10⁸ opérations simples/seconde) :

n = 1 000 000 éléments
─────────────────────────────────────────────
O(1)        1 op            instantané
O(log n)    ~20 ops         instantané
O(n)        10⁶ ops         ~10 ms
O(n log n)  2×10⁷ ops       ~0,2 s
O(n²)       10¹² ops        ~3 heures
O(2ⁿ)       10³⁰¹⁰³⁰ ops    jamais
─────────────────────────────────────────────
Passer de O(n²) à O(n log n) n'est pas une
optimisation : c'est la différence entre
« ça tourne » et « ça ne finira pas ».

Exemples canoniques : O(1) = accès tab[i], lookup de hash map. O(log n) = recherche dichotomique (on divise l’espace par 2 à chaque étape). O(n) = parcours de tableau, Math.max(...arr). O(n log n) = les bons tris (merge sort, et le Array.prototype.sort des moteurs modernes). O(n²) = double boucle sur la même collection (comparer toutes les paires). O(2ⁿ) = explorer tous les sous-ensembles, Fibonacci récursif naïf.

Comment ça marche

Temps vs espace. La complexité en temps compte les opérations ; la complexité en espace compte la mémoire supplémentaire allouée. Un merge sort est O(n log n) en temps mais O(n) en espace (tableaux temporaires) ; un tri en place comme heapsort est O(1) en espace. Piège fréquent : la récursion consomme de la pile — une descente récursive de profondeur n est O(n) en espace même sans allouer de tableau.

Meilleur, pire, moyen cas. Un même algorithme a plusieurs visages : quicksort est O(n log n) en moyenne mais O(n²) au pire (pivot systématiquement mauvais, ex. tableau déjà trié avec un pivot naïf) ; la recherche linéaire est O(1) au mieux (premier élément), O(n) au pire. Par défaut, Big O désigne le pire cas — sauf mention explicite, c’est lui qu’on annonce en entretien. Les hash maps sont l’exception qu’on cite en moyenne : O(1) moyen, O(n) au pire (toutes les clés en collision).

Complexité amortie. Un push sur un tableau dynamique (ArrayList, vector, tableau JS) est O(1)… sauf quand la capacité est pleine : il faut réallouer et tout recopier, O(n). Mais comme on double la capacité à chaque fois, ce coût se produit de plus en plus rarement : étalé sur N appels, le coût total reste proportionnel à N. On dit que le push est O(1) amorti — cher parfois, bon marché en moyenne garantie sur la séquence.

Les complexités des structures qu’on manipule tous les jours :

Structure	Accès index	Recherche	Insertion	Suppression
Tableau dynamique	O(1)	O(n)	O(1) amorti en fin, O(n) ailleurs	O(n) (décalage)
Liste chaînée	O(n)	O(n)	O(1) (nœud connu)	O(1) (nœud connu)
Hash map / Set	—	O(1) moyen, O(n) pire	O(1) moyen	O(1) moyen
Arbre équilibré (AVL, red-black)	—	O(log n)	O(log n)	O(log n)
Heap (priority queue)	O(1) le min/max	O(n)	O(log n)	O(log n) (racine)

💡 La question cachée derrière le tableau — « pourquoi une hash map est-elle O(1) ? » : la fonction de hachage transforme la clé en index de bucket, accès direct. Le O(n) au pire arrive quand trop de clés atterrissent dans le même bucket (collisions) — les bonnes implémentations redimensionnent pour l’éviter.

Concepts clés à maîtriser

Le piège n°1 en entretien : la boucle imbriquée cachée. includes, indexOf, find, le spread [...arr], concat, slice… sont tous des parcours O(n). En glisser un dans une boucle fabrique du O(n²) qui ne se voit pas :

// ❌ O(n × m) : includes() est un scan linéaire caché
//    → 10 000 × 10 000 = 10⁸ opérations, ça rame déjà
function communs(a, b) {
  return a.filter(x => b.includes(x));
}

// ✅ O(n + m) : on paie une construction de Set en O(m),
//    puis chaque test d'appartenance est O(1)
function communsRapide(a, b) {
  const setB = new Set(b);          // O(m), une seule fois
  return a.filter(x => setB.has(x)); // n tests en O(1)
}

Le refactoring type — « je troque de la mémoire (le Set, O(m) en espace) contre du temps » — est exactement la phrase attendue. Autres classiques du même piège :

Concaténation de strings dans une boucle : en Java/C#/Python, s += mot recopie la chaîne à chaque tour → O(n²). Utiliser un StringBuilder / "".join(liste).
delete/splice dans une boucle sur un tableau : chaque suppression décale le reste, O(n) par suppression.
Requête dans une boucle : le célèbre problème N+1 des ORM est la version base de données du O(n²) caché — une requête par élément au lieu d’un WHERE id IN (...).
Deux boucles successives ≠ imbriquées : for puis for = O(n + n) = O(n). Seule l’imbrication multiplie.

Et pour raisonner vite : une boucle simple sur n → O(n) ; deux boucles imbriquées sur la même entrée → O(n²) ; on divise le problème par 2 à chaque étape → O(log n) ; on fait un travail O(n) à chaque niveau d’une division par 2 → O(n log n) ; on essaie toutes les combinaisons → exponentiel.

🎤 En entretien — après CHAQUE exercice de code, la question tombe : « quelle est la complexité de ta solution ? ». Prenez les devants : annoncez-la vous-même en finissant (« c’est O(n) en temps, O(n) en espace à cause du Set »). Puis le bonus qui marque : « on pourrait descendre à O(1) en espace si le tableau était trié, avec deux pointeurs ». Anticiper la question, c’est elle qu’on vous posait vraiment.

En entretien

« Quelle est la complexité de la recherche dichotomique, et pourquoi ? » — O(log n) : chaque comparaison élimine la moitié de l’espace de recherche restant ; il faut log₂(n) divisions pour tomber à un élément (20 étapes pour un million). Condition indispensable : le tableau est trié — sinon on paie un tri O(n log n) avant.

« Pourquoi dit-on qu’on ne peut pas trier plus vite que O(n log n) ? » — C’est la borne inférieure des tris par comparaison : n! permutations possibles, chaque comparaison ne fait qu’un bit d’information, il faut log₂(n!) ≈ n log n comparaisons. Les tris non comparatifs (counting sort, radix sort) descendent à O(n + k) quand les clés s’y prêtent — le mentionner montre qu’on connaît la limite ET son contournement.

« Complexité amortie : c’est quoi, un exemple ? » — Le coût moyen garanti sur une séquence d’opérations, même si certaines sont chères. Exemple : push d’un tableau dynamique, O(1) amorti malgré des réallocations O(n) occasionnelles, parce que le doublement de capacité rend ces réallocations exponentiellement rares.

« Ton code est O(n²), comment l’améliorer ? » — La méthode : identifier l’opération répétée coûteuse (souvent une recherche O(n) dans la boucle), la remplacer par une structure à lookup O(1) (hash map/Set) ou pré-trier pour utiliser dichotomie/deux pointeurs. Le trade-off à énoncer : on échange de l’espace mémoire contre du temps.

« Quicksort est O(n²) au pire — pourquoi l’utilise-t-on quand même ? » — Parce que le pire cas est rarissime avec un pivot aléatoire ou médian, que ses constantes sont excellentes (cache-friendly, en place), et que O(n log n) moyen + bonnes constantes bat souvent un merge sort théoriquement plus sûr. Les libs réelles mitigent (introsort bascule sur heapsort si la récursion dégénère).

Pièges & idées reçues

⚠️ Big O n’est pas un chronomètre — O(n) avec une constante énorme (I/O, allocations) peut perdre contre un O(n²) compact sur des petites entrées. Big O prédit la croissance, pas la vitesse absolue : sur n = 20, l’algorithme « naïf » est souvent le bon choix (et le plus lisible).

Oublier l’espace : annoncer « O(n) » sans préciser temps ou espace. Une solution avec hash map est O(n) temps ET O(n) espace ; la version deux pointeurs sur tableau trié est O(1) espace. Toujours donner les deux.
La récursion « gratuite » : chaque appel empile un frame. Fibonacci récursif naïf est O(2ⁿ) en temps ET O(n) en espace de pile ; la mémoïsation le ramène à O(n).
sort() n’est pas gratuit : glisser un tri « pour simplifier » met un plancher O(n log n) à toute la solution. Le dire explicitement (« je trie d’abord, donc O(n log n) global »).
Confondre O, Θ, Ω : Big O est une borne supérieure. Dire « la recherche linéaire est O(n²) » est techniquement vrai mais inutile. En entretien, on emploie O comme « l’ordre de grandeur serré du pire cas » — c’est l’usage courant, savoir que Θ existe est un bonus.
Ignorer n vs m : avec deux entrées de tailles différentes, écrire O(n × m), pas O(n²) — précision qui compte pour un filter + includes sur deux tableaux distincts.

Pour aller plus loin

Big-O Cheat Sheet : le poster des complexités par structure et par tri
CLRS — Introduction to Algorithms chap. 3 : la définition formelle propre
NeetCode : s’entraîner à annoncer la complexité après chaque problème résolu
Mesurer soi-même : console.time() sur communs vs communsRapide avec 10 000 éléments — voir un O(n²) mourir en vrai vaut tous les cours

The essentials

Big O notation describes how an algorithm’s cost (time or memory) grows with the input size n. It doesn’t measure seconds: it predicts scaling. An algorithm that’s fast on 100 elements but O(n²) will blow up on a million — and that’s exactly what an interviewer wants to check: do you see the explosion coming before production?

Big O keeps the dominant term and drops constants: 3n² + 50n + 1000 → O(n²). For small n, constants win (insertion sort beats merge sort on 10 elements); asymptotically, the complexity class always wins.

The scale to know, with a concrete order of magnitude (≈10⁸ simple operations/second):

n = 1,000,000 elements
─────────────────────────────────────────────
O(1)        1 op            instant
O(log n)    ~20 ops         instant
O(n)        10⁶ ops         ~10 ms
O(n log n)  2×10⁷ ops       ~0.2 s
O(n²)       10¹² ops        ~3 hours
O(2ⁿ)       10³⁰¹⁰³⁰ ops    never
─────────────────────────────────────────────
Going from O(n²) to O(n log n) is not an
optimization: it's the difference between
"it runs" and "it will never finish".

Canonical examples: O(1) = arr[i] access, hash map lookup. O(log n) = binary search (halve the space at every step). O(n) = array traversal, Math.max(...arr). O(n log n) = the good sorts (merge sort, and modern engines’ Array.prototype.sort). O(n²) = double loop over the same collection (compare all pairs). O(2ⁿ) = exploring all subsets, naive recursive Fibonacci.

How it works

Time vs space. Time complexity counts operations; space complexity counts the extra memory allocated. Merge sort is O(n log n) in time but O(n) in space (temporary arrays); an in-place sort like heapsort is O(1) in space. Frequent trap: recursion consumes stack — a recursive descent of depth n is O(n) in space even without allocating a single array.

Best, worst, average case. The same algorithm has several faces: quicksort is O(n log n) on average but O(n²) worst case (systematically bad pivot, e.g. an already-sorted array with a naive pivot); linear search is O(1) at best (first element), O(n) at worst. By default, Big O refers to the worst case — unless stated otherwise, that’s what you announce in an interview. Hash maps are the exception quoted on average: O(1) average, O(n) worst (all keys colliding).

Amortized complexity. A push on a dynamic array (ArrayList, vector, JS array) is O(1)… except when capacity is full: reallocate and copy everything, O(n). But since capacity doubles each time, that cost happens increasingly rarely: spread over N calls, total cost stays proportional to N. We say push is amortized O(1) — occasionally expensive, guaranteed cheap on average over the sequence.

The complexities of the structures we handle every day:

Structure	Index access	Search	Insertion	Deletion
Dynamic array	O(1)	O(n)	Amortized O(1) at end, O(n) elsewhere	O(n) (shifting)
Linked list	O(n)	O(n)	O(1) (known node)	O(1) (known node)
Hash map / Set	—	O(1) avg, O(n) worst	O(1) avg	O(1) avg
Balanced tree (AVL, red-black)	—	O(log n)	O(log n)	O(log n)
Heap (priority queue)	O(1) min/max	O(n)	O(log n)	O(log n) (root)

💡 The hidden question behind the table — “why is a hash map O(1)?”: the hash function turns the key into a bucket index, direct access. The O(n) worst case happens when too many keys land in the same bucket (collisions) — good implementations resize to avoid it.

Key concepts to master

Interview trap number one: the hidden nested loop. includes, indexOf, find, the spread [...arr], concat, slice… are all O(n) traversals. Slipping one inside a loop manufactures invisible O(n²):

// ❌ O(n × m): includes() is a hidden linear scan
//    → 10,000 × 10,000 = 10⁸ operations, already sluggish
function common(a, b) {
  return a.filter(x => b.includes(x));
}

// ✅ O(n + m): we pay a Set construction in O(m),
//    then every membership test is O(1)
function commonFast(a, b) {
  const setB = new Set(b);          // O(m), once
  return a.filter(x => setB.has(x)); // n tests in O(1)
}

The typical refactor — “I trade memory (the Set, O(m) space) for time” — is exactly the expected sentence. Other classics of the same trap:

String concatenation in a loop: in Java/C#/Python, s += word copies the string each iteration → O(n²). Use a StringBuilder / "".join(list).
delete/splice in a loop over an array: each removal shifts the rest, O(n) per removal.
A query inside a loop: the famous ORM N+1 problem is the database version of hidden O(n²) — one query per element instead of a single WHERE id IN (...).
Two successive loops ≠ nested: for then for = O(n + n) = O(n). Only nesting multiplies.

And to reason fast: one simple loop over n → O(n); two nested loops over the same input → O(n²); halving the problem at each step → O(log n); doing O(n) work at each level of a halving → O(n log n); trying every combination → exponential.

🎤 In an interview — after EVERY coding exercise, the question drops: “what’s the complexity of your solution?”. Get ahead of it: announce it yourself as you finish (“it’s O(n) time, O(n) space because of the Set”). Then the bonus that scores: “we could get to O(1) space if the array were sorted, with two pointers”. Anticipating the question is what they were really testing.

In an interview

“What’s the complexity of binary search, and why?” — O(log n): each comparison eliminates half of the remaining search space; you need log₂(n) halvings to reach one element (20 steps for a million). Non-negotiable precondition: the array is sorted — otherwise you pay an O(n log n) sort first.

“Why do people say you can’t sort faster than O(n log n)?” — It’s the lower bound for comparison-based sorts: n! possible permutations, each comparison yields one bit of information, so you need log₂(n!) ≈ n log n comparisons. Non-comparison sorts (counting sort, radix sort) get to O(n + k) when the keys allow it — mentioning that shows you know both the limit AND its workaround.

“Amortized complexity: what is it, give an example?” — The guaranteed average cost over a sequence of operations, even if some are expensive. Example: a dynamic array push, amortized O(1) despite occasional O(n) reallocations, because capacity doubling makes those reallocations exponentially rare.

“Your code is O(n²), how would you improve it?” — The method: identify the expensive repeated operation (often an O(n) search inside the loop), replace it with an O(1)-lookup structure (hash map/Set) or pre-sort to use binary search/two pointers. The trade-off to state: you exchange memory space for time.

“Quicksort is O(n²) worst case — why is it still used?” — Because the worst case is vanishingly rare with a random or median pivot, its constants are excellent (cache-friendly, in place), and average O(n log n) + good constants often beats a theoretically safer merge sort. Real libraries mitigate it (introsort switches to heapsort if recursion degenerates).

Pitfalls & misconceptions

⚠️ Big O is not a stopwatch — O(n) with a huge constant (I/O, allocations) can lose to a compact O(n²) on small inputs. Big O predicts growth, not absolute speed: at n = 20, the “naive” algorithm is often the right choice (and the most readable).

Forgetting space: announcing “O(n)” without saying time or space. A hash-map solution is O(n) time AND O(n) space; the two-pointer version on a sorted array is O(1) space. Always give both.
“Free” recursion: every call pushes a stack frame. Naive recursive Fibonacci is O(2ⁿ) time AND O(n) stack space; memoization brings it down to O(n).
sort() isn’t free: slipping in a sort “to simplify” puts an O(n log n) floor under the whole solution. Say it explicitly (“I sort first, so O(n log n) overall”).
Confusing O, Θ, Ω: Big O is an upper bound. Saying “linear search is O(n²)” is technically true but useless. In interviews, O is used as “the tight order of magnitude of the worst case” — that’s common usage; knowing Θ exists is a bonus.
Ignoring n vs m: with two inputs of different sizes, write O(n × m), not O(n²) — a precision that matters for a filter + includes over two distinct arrays.

Going further

Big-O Cheat Sheet: the poster of complexities per structure and per sort
CLRS — Introduction to Algorithms ch. 3: the clean formal definition
NeetCode: practice announcing the complexity after every solved problem
Measure it yourself: console.time() on common vs commonFast with 10,000 elements — watching an O(n²) die for real is worth every lecture

S'entraîner sur ce sujet → Practice this topic →