Cum se determină timpul necesar pentru inserarea unui element la sfârșitul unui slice într-un limbaj de programare?

În limbajul Go, slice-ul este o structură care conține un pointer către un array, o lungime și o capacitate.

Inserarea unui element la sfârșitul slice-ului se face de obicei prin operația append:

slice = append(slice, newElement)

Timpul de inserare depinde de dacă capacitatea curentă a slice-ului este suficientă pentru noul element:

• Dacă capacitatea este suficientă, append scrie pur și simplu elementul în următorul slot liber — operație O(1).
• Dacă capacitatea nu este suficientă, se alocă un nou array cu o capacitate mărită, se copiază elementele vechi și se adaugă noul element — operație O(n), unde n este lungimea curentă a slice-ului.

Astfel, timpul amortizat de inserție la sfârșitul slice-ului este O(1), deși unele operații pot fi mai costisitoare din cauza redistribuirii memoriei.