Como é avaliada a complexidade temporal da operação de busca de um elemento por valor numa sequência do tipo slice?

A complexidade temporal de procurar um elemento por valor numa fatia (slice) em Go é O(n), onde n é o número de elementos na fatia.

Isto deve-se ao fato de que uma fatia é uma sequência ordenada de elementos sem uma estrutura indexada para uma busca rápida. Para encontrar um elemento, é necessário percorrer a fatia sequencialmente, comparando cada elemento com o valor procurado.

Exemplo de busca de um elemento na fatia:

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

Se for necessária uma busca mais rápida, deve-se usar estruturas de dados com acesso indexado, como um mapa.