GabaritoB — O(n).
Gabarito: letra B — O(n). Para inserir um elemento em uma posição que não está nas extremidades, é necessário percorrer a lista até encontrar o nó anterior à posição desejada, o que exige tempo linear O(n) no pior caso. A operação de inserção em si (ajuste dos ponteiros) é O(1), mas o custo dominante é a busca do ponto de inserção.
A questão testa a diferença entre a complexidade das operações em listas encadeadas: inserir no início ou fim é O(1); inserir em posição arbitrária requer percurso, resultando em O(n). Vejamos cada alternativa:
O(1) só é possível para inserção no início ou no fim, quando se possui referência direta. Para posições intermediárias, a lista deve ser percorrida.
Conforme explicado, encontrar o local leva tempo proporcional ao número de elementos no pior caso, ou seja, O(n).
O(n log n) é típico de algoritmos de ordenação eficientes, não se aplica à inserção em lista encadeada.
O(log n) ocorre em estruturas que permitem busca binária (arrays ordenados ou árvores balanceadas), não em listas lineares.
O(log n²) é equivalente a O(2 log n) = O(log n) na notação assintótica, e não corresponde à complexidade da operação.
A pegadinha clássica é confundir o custo da inserção (O(1) após achar o nó) com o custo total da operação, que inclui a busca. Lembre-se: manipular ponteiros é rápido; encontrar a posição é que custa caro. Treine essa distinção para não cair nela na prova!
Gabarito: letra B — O(n).
Link permanente: /questoes/qg615403