O (1) : constante – mais rápido, impossível;
O (log log n) : super-rápido;
O (log n) : logarítmico – muito bom;
O (n) : linear – é o melhor que se pode esperar se algo não pode ser determinado sem examinar toda a entrada;
O (n log n) : limite de muitos problemas práticos, ex.: ordenar uma coleção de números;
O (n²) : quadrático;
O (n^k) : polinomial – ok para n pequeno;
O (k^n), O (n!), O (nn) : exponencial – evite!
1 < log n < n < n log n < n² < n³ < n99 < 2^n < 3^n
Fonte: http://www.inf.ufrgs.br/~prestes/Courses/Complexity/aula1.pdf
.
Resposta: Letra D
-> O(log2 n); O(n.log2 n); O(n²); O(n³); O(2^n), ou seja, O(log2 n) < O(n.log2 n) < O(n²) < O(n³) < O(2^n)...
Copiei um comentário de um brother aqui do QC
Constante - O (1): É único caso onde as instruções dos algoritmos são executadas num tamanho fixo de vezes. Ex: Algoritmo que identifica se um número é par ou ímpar;
Logaritmo - O(log n) : Ocorre tipicamente em algoritmos que dividem problemas em problemas menores. Ex: Algoritmo de busca binária, buscar um elemento em um vetor ordenado;
Linear - O (n): Uma operação básica é executada em cada elemento de entrada do algoritmo. Ex: Busca sequêncial;
O(n log n): Dividem problemas em problemas menores, porém juntando posteriormente a solução dos problemas menores. Ex: Merge Sort;
Quadrática - O(n²): Os itens são processados aos pares, 2 laços aninhados. Ex: Somatório de duas matrizes (2 laços aninhados);
Cúbica - O(n³): Os itens são processados três a três, com 3 laços aninhados. Ex: Multiplicação de matrizes (3 laços aninhados);
Exponencial - O a de n: Algoritmos muitos custosos, possuem pouca aplicação prática. Ex: Algoritmos de força bruta que testam todas as possibilidades;