Os números 1,2,3,...,N foram inseridos de forma ordenada em ...

A alternativa correta é a E.

Para entender por que essa é a resposta correta, vamos analisar o comportamento e os tempos de busca em cada uma das estruturas mencionadas: a árvore binária de busca, a árvore AVL e o vetor.

Árvore Binária de Busca (BST)

Na árvore binária de busca, os números 1, 2, 3, ..., N foram inseridos de forma ordenada. Isso significa que a árvore estará desequilibrada, com todos os nós à direita do nó anterior, formando uma estrutura semelhante a uma lista encadeada. O tempo de busca em uma árvore binária de busca desequilibrada é O(N), no pior caso.

Árvore AVL

Em uma árvore AVL, que é uma árvore binária de busca auto-balanceada, a inserção de elementos mantém a árvore equilibrada. Isso garante que a altura da árvore seja aproximadamente O(log N). Portanto, o tempo de busca em uma árvore AVL é O(log N).

Vetor

Para o vetor, foi decidido que a posição do número i seria dada pelo índice i-1. Isso significa que cada elemento pode ser acessado diretamente por seu índice. O tempo de busca em um vetor, quando sabemos o índice, é O(1), pois é uma operação de acesso direto.

Agora, vamos justificar as alternativas incorretas:

A - O(log N), O(log N), O(N)

Essa alternativa está incorreta porque o tempo de busca em um vetor é O(1), não O(N).

B - O(log N), O(log N), O(1)

Essa alternativa está incorreta porque o tempo de busca em uma árvore binária de busca desequilibrada é O(N), não O(log N).

C - O(log N), O(1), O(log N)

Essa alternativa está incorreta porque o tempo de busca em uma árvore AVL é O(log N), e não O(1).

D - O(N), O(log N), O(log N)

Essa alternativa está incorreta porque o tempo de busca em um vetor é O(1), não O(log N).

Portanto, a alternativa correta é de fato a E, que reflete corretamente os tempos de busca em cada uma das estruturas: O(N) para a árvore binária de busca, O(log N) para a árvore AVL e O(1) para o vetor.

Busca Binária Ordenada: O(N)

Busca AVL: O(Log N)

Vetor pelo índice i-1: O(1) 

A pegadinha estava na busca pelo índice. Do contrário, seria busca sequencia, de complexidade O(N)

A busca binária ordenada tem complexidade O(n) porque os elementos não estão distribuídos de forma a conter raiz, filhos à direita e/ou filhos à esquerda, impossibilitando a aplicação da busca por complexidade o(log n). É como se os elementos fossem dispostos em forma direta ou zigue-zague. Dessa forma, para encontrar um elemento é necessário passar por todos os demais, tendo a complexidade linear, no pior caso.

A árvore de busca AVL terá a complexidade o(log N) justamente por poder dividir por 2 seus elementos até encontrar o valor de busca.

O vetor tem complexidade O(1) porque pode ser buscado diretamente pelo seu índice. Ex: lista[0] busca o primeiro elemento do vetor.

arvores geralmente sao O (log n) tanto melhor como pior caso. so lembrar que log (toco) vem da arvore.

array: melhor caso: 1 (ordem ascendente). pior: (N).