Dado o algoritmo recursivo abaixo, assinale a alternativa que melhor define a equação de recorrência.

A resposta correta é: “” Justificativa: Caso inf seja igual ou maior que sup, o tamanho da entrada n é menor ou igual a 1. Nesse caso, o algoritmo entrará no “senão” da linha 9 e retornará -1, garantindo Θ(1). Caso n seja maior que 1, dentre outras instruções constantes, ele entrará numa chamada recursiva, passando metade dos elementos n/2. Assim, temos a equação de recursiva para n > 1 que é T(n) = T((n / 2)) + Θ(1). Repare que, pela notação assintótica, Θ(1) = Θ(2) = Θ(3) = ..., podendo-se simplificar as instruções que não dependem de n para simplesmente Θ(1).