GabaritoB — N;
Gabarito: letra B. Em uma lista encadeada simples, não ordenada e sem ponteiro para o último elemento, a inserção no final exige percorrer todos os N nós para localizar o fim, resultando em complexidade O(N). Se a inserção fosse no início, seria O(1), mas isso não é o padrão assumido pela questão.
A complexidade O(log N) é típica de buscas em estruturas balanceadas (como árvores binárias) ou de algoritmos de divisão e conquista, não se aplica à inserção em lista encadeada, que é sequencial.
Inserir em uma lista encadeada não ordenada, quando não se mantém referência ao final, requer percorrer todos os elementos até o último nó (ou até a posição desejada, caso seja no meio). Isso gera complexidade linear O(N).
O(N log N) é a complexidade média de algoritmos de ordenação eficientes (como Merge Sort ou Quick Sort), não de inserção em listas.
O(N²) é típica de algoritmos de ordenação ineficientes (Bubble Sort, Selection Sort) ou de aninhamento de loops; não é o caso da inserção em lista.
A inserção no início de uma lista encadeada é O(1), mas a questão não especifica o local da inserção. Na interpretação mais comum (inserção no final ou em posição arbitrária sem referência direta), a complexidade é O(N). A banca explora a confusão entre esses dois cenários.
O candidato pode associar erroneamente que toda inserção em lista encadeada é O(1), esquecendo que isso só vale para o início. Sem um ponteiro explícito para o final, a inserção no fim exige percorrer a lista, levando a O(N). Lembre-se: em provas, sempre considere o pior caso se não houver detalhamento.
Gabarito: letra B
Link permanente: /questoes/fg048867