Questões de Algoritmos e Estrutura de Dados - Complexidade de Algoritmos para Concurso

Considere o seguinte pseudocódigo, no qual uma rotina com complexidade O(n) é aplicada em um laço duplo.

                              PARA i ←1 ATÉ n FAÇA
                                          INÍCIO
                                                    PARA j ←1 ATÉ i FAÇA
                                                               INÍCIO
                              rotina com complexidade O(n);
                                                       FIM;
                                            FIM PARA;
                                     FIM;
                         FIM PARA;

A pesquisa de dados envolve a determinação da chave pesquisada estar ou não entre os dados pesquisados e, caso  esteja, que seja encontrada sua localização. Em computação, a pesquisa tem um papel importante, pois de posse do  campo chave a ser pesquisado fica mais fácil encontrar determinado arquivo, ou mesmo qualquer item que se queira  buscar.  Já  a  classificação  envolve  a  organização  dos  dados  em  uma  determinada  ordem,  por  exemplo:  crescente,  decrescente, ordem alfabética, numérica, entre outros. Acerca dos algoritmos de pesquisa e classificação, analise as  afirmativas a seguir.

I. Diz-se que o algoritmo 0(log n) tem um tempo de execução linear.
II. A pesquisa binária executa em 0(log n) vezes, pois cada passo remove metade dos elementos restantes. 
III. O algoritmo de classificação por inserção executa no tempo 0(n²), no pior caso e no caso médio. 
IV.No pior caso, a primeira chamada à classificação por intercalação tem de fazer 0(n) comparações para preencher os n slots no array final. 

Estão corretas apenas as afirmativas 

O algoritmo de ordenação de pior complexidade temporal no caso médio, dentre os que se seguem, é

Os números 1,2,3,...,N foram inseridos de forma ordenada em uma árvore binária de busca, em uma árvore AVL e em um vetor para o qual foi decidido que a posição do número i seria dada pelo índice i-1. Depois, sabendo-se que nenhuma inserção posterior será realizada em nenhuma das três estruturas, decidiu-se fazer uma busca em cada uma destas. Os tempos que se podem obter para essa busca na árvore binária de busca, na árvore AVL e no vetor são, respectivamente,

Sobre a análise de algoritmos, é CORRETO afirmar que