Jak określić czas potrzebny na dodanie elementu na koniec wycinka (slice) w języku programowania?

W języku Go, zakres (slice) to struktura zawierająca wskaźnik na tablicę, długość i pojemność.

Wstawianie elementu na koniec zakresu zwykle odbywa się za pomocą operacji append:

slice = append(slice, newElement)

Czas wstawiania zależy od tego, czy obecna pojemność zakresu jest wystarczająca dla nowego elementu:

• Jeśli pojemność jest wystarczająca, append po prostu zapisuje element w następnej wolnej pozycji — operacja O(1).
• Jeśli pojemność nie jest wystarczająca, alokowany jest nowy array z powiększoną pojemnością, stare elementy są kopiowane, a nowy jest dodawany — operacja O(n), gdzie n to obecna długość zakresu.

W związku z tym, amortyzowany czas wstawiania na koniec zakresu to O(1), choć niektóre operacje mogą być droższe z powodu redystrybucji pamięci.