Quelle est la complexité temporelle de l'opération d'insertion d'un nouvel élément dans un tableau?

L'insertion d'un nouvel élément dans un tableau a une complexité temporelle de O(n) dans le pire des cas, où n est le nombre d'éléments dans le tableau.

La raison en est que le tableau a une taille fixe, et pour insérer un élément au milieu ou au début, il faut décaler tous les éléments suivants d'une position vers la droite. Si l'insertion se fait à la fin et qu'il y a de l'espace libre, l'opération peut être O(1).

Exemple :

• Insertion à la fin avec de l'espace disponible : O(1)
• Insertion au début ou au milieu : O(n) en raison du décalage des éléments

Dans les tableaux dynamiques (par exemple, ArrayList en Java), lorsque le tableau est plein, une copie est effectuée dans un nouveau tableau de taille supérieure, ce qui nécessite également O(n) en temps.