Question

A análise de complexidade de algoritmos estuda a capacidade de execução avaliando o desempenho dos algoritmos. A análise permite projetar o desempenho de algoritmos sem a necessidade de executa-los.

GOODRICH, Michael T.; TAMASSIA, Roberto; GOLDWASSER, Michael H. Data structures and algorithms in Java. John Wiley & Sons, 2014.



Analise o algoritmo:



int metodo (T vetor[], T chave, int n) {

int w = 0;

while ((w < n) && (vetor[w] < chave))

w++;

if ((w < n) && (vetor[w] == chave))

return w;

else

return -1;

Considerando o contexto, assinale a alternativa correta.

Escolha uma:
a.
Considerando a notação Ω (Big Omega), o tempo de execução é Ω (log n).

b.
Existem casos na execução algoritmo em que a operação de comparação não é executada.

c.
O desempenho do algoritmo depende da variável chave.

d.
Considerando o melhor caso, a variável w não será incrementada.

e.
Considerando o pior caso, o tempo de execução é O(n).

Answer 1

Resposta:

e.

Considerando o pior caso, o tempo de execução é O(n).

Explicação:

Corrigido pelo AVA.

Answer 2

Resposta:

Considerando o pior caso, o tempo de execução é O(n)

Explicação:

PIOR CASO, ELEMENTO NÃO ENCONTRADO NO VETOR