Question

2.Supondo uma pesquisa de um elemento em um vetor desordenado, qual a complexidade de tempo para o pior caso? E se este vetor estivesse ordenado de forma crescente a complexidade mudaria? Se sim qual seria ela?

Answer 1

Sim, a complexidade mudaria pois veja bem:

Em um vetor desordenado seria necessário percorre-lo todo para verificar se o elemento existe ou não, já com o modo ordenado você pode fazer uma busca que inicie ao meio do vetor onde será sempre feito duas comparações e a cada ciclo ele quebra pela metade a quantidade de elementos, por exemplo:

V = [1,2,3,4,5,6,7,8,9,10]
Busca por 8

1° Loop: Seleciona 5
Verifica 8 é > ou < que 5 ? Maior

2° Loop: Seleciona 8
Verifica 8 é = 8 ? Sim, retorna o valor

Portanto para vetores desordenados a complexidade no pior caso é O(n) enquanto para ordenados (desde que a busca não seja linear) é O(log n)

Espero ter ajudado :)