Ako určiť časovú zložitosť operácie odstránenia prvku z poľa typu slice?

V Go je slice štruktúra, ktorá obsahuje ukazovateľ na pole, dĺžku a kapacitu. Pri odstraňovaní prvku zo slice je zvyčajne potrebné posunúť všetky nasledujúce prvky o jednu pozíciu doľava, aby sa vyplnila "diera".

Časová zložitosť tejto operácie je O(n), kde n je počet prvkov po odstránenom prvku. To je spôsobené tým, že je potrebné skopírovať (n - index_odstráneného - 1) prvkov.

Príklad odstránenia prvku podľa indexu:

func remove(slice []int, i int) []int {
    return append(slice[:i], slice[i+1:]...)
}

Tu append kopíruje prvky z slice[i+1:] na pozíciu za slice[:i], čo vyžaduje lineárny čas v závislosti od počtu kopírovaných prvkov.