Como determinar a complexidade temporal de uma função que procura o primeiro elemento num array que não está presente noutro?

Para determinar a complexidade temporal de uma função que procura o primeiro elemento no array A que não está no array B, é necessário analisar o algoritmo:

1. Se para cada elemento do array A verificamos a sua presença no array B por uma busca linear (por exemplo, com um ciclo), então para cada elemento de A realizamos uma busca em B — isto é O(n) por cada elemento, onde n é o tamanho do array B. Se o tamanho de A é m, a complexidade total será O(m * n).

2. Se, por outro lado, criarmos uma estrutura de dados para buscas rápidas, como um HashSet dos elementos do array B (em O(n)), a verificação da presença de um elemento será em média O(1). Assim, o algoritmo completo será:

• Criar um HashSet a partir do array B — O(n)
• Percorrer os elementos do array A e verificar a sua presença no HashSet — O(m)

A complexidade temporal total é — O(m + n).

Exemplo em Kotlin:

fun findFirstMissing(a: List<Int>, b: List<Int>): Int? {
    val setB = b.toHashSet() // O(n)
    for (element in a) { // O(m)
        if (element !in setB) {
            return element
        }
    }
    return null
}

Assim, a complexidade temporal depende da implementação e pode variar de O(m * n) até O(m + n).