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;
Fonte: Minhas anotações baseadas nas Apostilas do Estratégia Concurso.
1- f(n) = O(1) – Complexidade constante
2- f(n) = O(log n) – Complexidade sub-linear ou logarítmica
3- f(n) = O(n) – Complexidade linear
4 - f(n) = O(n log n) – Sub-divisão de problema (Exe.: MergeSort e QuikSort)
5 - f(n) = O(n^2) – Complexidade polinomial
6 - f(n) = O(2^n) – Complexidade exponencial
7 - f(n) = O(n!) – Complexidade fatorial