Peut-on expliquer ce que signifie la complexité temporelle d'un algorithme égale à O(n) ?

La complexité temporelle d'un algorithme, égale à O(n), signifie que le temps d'exécution de l'algorithme augmente linéairement avec la taille des données d'entrée n. Si le nombre d'éléments double, le temps de fonctionnement double également environ.

Par exemple, si vous avez une boucle qui parcourt tous les éléments d'un tableau de n éléments, c'est un cas typique de O(n) :

void PrintElements(int[] arr) {
    for (int i = 0; i < arr.Length; i++) {
        Console.WriteLine(arr[i]);
    }
}

Ici, le temps d'exécution dépend directement du nombre d'éléments dans le tableau.