Qual é a complexidade temporal da operação de busca de um elemento numa lista implementada através de um slice?

Em Go, um slice é um array dinâmico que armazena elementos numa área de memória sequencial. A busca de um elemento por valor num slice requer percorrer os elementos, uma vez que o slice não é indexado por valor.

Assim, a complexidade temporal da operação de busca de um elemento num slice é O(n), onde n é o número de elementos no slice.

Exemplo de busca de um elemento:

func contains(slice []int, val int) bool {
    for _, item := range slice {
        if item == val {
            return true
        }
    }
    return false
}

Aqui, no pior caso, será necessário verificar todos os elementos.