Assinale a complexidade do algoritmo empregado.

O pseudocódigo a seguir serve de referência para as duas próximas questões.

function xpto (k as integer, L[] as integer,

tamanho as integer) as integer

n1 = 1;

n2 = tamanho;

x = (n1 + n2) \ 2;

while n1 < n2 and L[x] <> k

begin

if k < L[x] then

n2 = x - 1

else

n1 = x + 1

endif;

x = (n1 + n2) // 2;

end;

if k == L[x] then

return x

else

return -1

endif;

É dado que a indexação do array de inteiros começa em 1, que o operador “\” denota a divisão inteira, e que o array deve estar ordenado em ordem crescente, sem duplicações