Insertion (3)
Analysis (counting copies):
Let n = right – left + 1 be the length of the array.
Step 2 performs 1 copy.
Step 1 performs between 0 and n–1 copies, say (n–1)/2 copies on average.
Average no. of copies = (n – 1)/2 + 1 = n/2 + 1/2
Time complexity is O(n).
Diapositive précédente
Diapositive suivante
Revenir à la première diapositive
Afficher la version graphique