Le Big O, pourquoi et comment

Le Big O mesure comment le coût d'un algorithme grandit avec la taille de l'entrée n, indépendamment de la machine.

Ce n'est pas un temps en secondes mais une tendance : elle permet de comparer deux approches avant même de coder, et de savoir si une solution tiendra sur n = 10⁶.

Les complexités à connaître#

Astuce : un processeur exécute environ 10⁸ à 10⁹ opérations simples par seconde. Avec n = 10⁵, un O(n²) (10¹⁰) est déjà trop lent : il faut viser O(n log n) ou mieux.

Les reconnaître dans le code#

function first(arr: number[]): number {          // O(1) : ne dépend pas de n
  return arr[0];
}

function sum(arr: number[]): number {            // O(n) : une boucle
  let total = 0;
  for (const x of arr) total += x;
  return total;
}

function hasDuplicate(arr: number[]): boolean {  // O(n²) : deux boucles imbriquées
  for (let i = 0; i < arr.length; i++)
    for (let j = i + 1; j < arr.length; j++)
      if (arr[i] === arr[j]) return true;
  return false;
}

function halvings(n: number): number {           // O(log n) : n divisé par 2 à chaque tour
  let steps = 0;
  while (n > 1) { n = Math.floor(n / 2); steps++; }
  return steps;
}

Règles de calcul#

• Des étapes à la suite s'additionnent, on garde le terme dominant : O(n) + O(n²) → O(n²).
• Des étapes imbriquées se multiplient : une boucle de n contenant une boucle de m → O(n × m).
• On ignore les constantes : O(2n) et O(n/2) sont des O(n).
• Une récursion qui se dédouble à chaque niveau (f(n-1) + f(n-2)) est en général O(2ⁿ).

Complexité spatiale#

Même logique pour la mémoire supplémentaire (hors entrée) : un tableau auxiliaire de taille n → O(n) ; quelques variables → O(1). La pile d'appels d'une récursion compte : une récursion de profondeur n coûte O(n) d'espace.

Cas pratique : en entretien, énoncez toujours la complexité en temps et en espace de votre solution, puis dites ce qui la limite. « O(n) en temps, O(n) en espace à cause du hashmap » montre que vous maîtrisez les compromis.

Pour aller plus loin#

• Big-O Notation - For Coding Interviews — NeetCode