Tenho uma dúvida, pela aula havia entendido que o insertion sort era O(n²), mas na tabela na atividade 5 está como O(n). Qual é o Big O do insertion sort?
Você está vendo a versão anterior da nova experiência da Alura que estamos preparando para você. Em breve, ela ganha uma identidade visual novinha totalmente pensada em potencializar seus estudos!
Tenho uma dúvida, pela aula havia entendido que o insertion sort era O(n²), mas na tabela na atividade 5 está como O(n). Qual é o Big O do insertion sort?
Olá Wagner! Tudo bem?
Peço desculpa pela demora para responder o seu tópico.
O insertion sort é um algoritmo de ordenação que possui complexidade O(n²) no pior caso. Porém, no melhor caso, quando o vetor já está ordenado, a complexidade é O(n).
Na tabela da atividade 5, foi provavelmente considerado o melhor caso para o insertion sort. Mas é importante lembrar que, na prática, é difícil que um vetor já esteja completamente ordenado antes de ser ordenado novamente.
Espero ter ajudado a esclarecer sua dúvida.
Bons estudos!