Come determinare la complessità temporale dell'operazione di rimozione di un elemento da un array di tipo slice?

In Go, uno slice è una struttura che contiene un puntatore a un array, una lunghezza e una capacità. Quando si rimuove un elemento da uno slice, di solito è necessario spostare tutti gli elementi successivi di una posizione a sinistra per riempire il "buco".

La complessità temporale di questa operazione è O(n), dove n è il numero di elementi dopo quello rimosso. Ciò è dovuto al fatto che bisogna copiare (n - indice_rimosso - 1) elementi.

Esempio di rimozione di un elemento per indice:

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

Qui, append copia gli elementi di slice[i+1:] nella posizione dopo slice[:i], il che richiede tempo lineare in funzione del numero di elementi copiati.