Question

Considere o seguinte trecho de algoritmo, representado em pseudocódigo:

1 - para i←1 até n faça

2 - para j←1 até n faça

3 - V[i][j]←i+j.

Nesse contexto, avalie as afirmações a seguir e selecione a alternativa correta dentre as disponíveis.

I - O número de instruções executadas pelo trecho de algoritmo é exatamente 2n2+2n+1.

II - Quando o tamanho da instância de entrada dobra, o número de instruções executadas é multiplicado por dois.

III - Sob a ótica da análise da eficiência assintótica, o tempo de execução do trecho de algoritmo é proporcional a T(n)=n2.

IV - Pode-se classificar o tempo de execução do trecho de algoritmo como linear no tamanho da entrada.

Answer 1

Resposta:

I e III

Explicação:

O número de instruções executadas pelo trecho de algoritmo é exatamente 2n2+2n+1.

- Sob a ótica da análise da eficiência assintótica, o tempo de execução do trecho de algoritmo é proporcional a T(n)=n2.