Que fait cet algorithme ? Donner sa complexité en fonction de la taille de la liste notée `n`.
Fonction INSERER(liste, x, i) :
Si (i >= longueur(liste)) :
Retourner Faux
Sinon : Créée un emplacement vide dans la liste
Pour k allant de longueur(liste)-1 à i avec un pas de -1 :
L(k) = L(k-1)
L(i) = x
Retourner Vrai
Cet algorithme permet d'insérer un élément dans une liste. Pour cela il vérifie que l'emplacement d'insertion n'est pas en dehors de la liste. Sinon, il décale tous les éléments au-delà de l'emplacement d'insertion et inscrit la valeur x à insérer à son emplacement i. On constate que cet algorithme parcours une fois la liste (même moins que la liste). Il s'agit donc d'une complexité linéaire en `O(n)`.