Escreva um algoritmo que receba valores em um vetor e imprima “ORDENADO” se o vetor estiver em ordem crescente. Qual é função de custo de pior caso e sua ordem de complexidade O ?

Passo 1

O exercício pede um algoritmo que recebe um vetor de tamanho n e imprime “ORDENADO” se o vetor estiver em ordem crescente. O conteúdo envolve verificação de ordenação e análise de custo, e vamos precisar contar quantas comparações de elementos adjacentes são feitas.

Passo 2

A estratégia é percorrer o vetor do segundo elemento até o último, comparando cada elemento com o seu antecessor. Se em alguma dessas comparações encontrarmos um valor menor que o anterior, concluímos que o vetor não está ordenado e podemos terminar a execução. Caso nenhuma dessas comparações falhe, imprimimos “ORDENADO”.
Em pseudocódigo fica assim:
for i de 1 até n-1:
se vetor[i] < vetor[i-1] então
retorne // vetor não está ordenado
fim do for
imprime “ORDENADO”

Passo 3

No pior caso, o vetor já está ordenado e, portanto, todas as comparações de pares adjacentes serão efetuadas. Há exatamente n-1 pares adjacentes em um vetor de tamanho n, logo realizamos n-1 comparações.
Dessa forma, a função de custo de pior caso é C(n)=n-1. Na notação assintótica, desprezamos constantes e termos de ordem inferior, ficando a complexidade como O(n).

Resposta

A função de custo de pior caso é C(n)=n-1 e a ordem de complexidade é O(n).

Exercícios relacionados