Visto esse conceito sobre complexidade e notação O, vamos ver agora qual é a complexidade de um algoritmo eficiente e qual a complexidade de ordenar um conjunto de elementos. Algoritmo eficiente 1) O(1) - Eficiente 2) O(n) - -> Qualquer algoritmo deve ser considerado eficiente se ele tiver complexidade polinominal. f(x) = O(n^c) onde c = cte. c = 1, 2, 3... Não eficiente: -> f'(x) = O(2^n) n 2^n e n^2 1 2 1 2 4 4 3 8 9 4 16 16 5 32 25 6 64 36 7 128 49 f'(x) = 2^n e f(x) = n^2 Ou seja, f(x) = O(f'(x)) <-> n^2 = O(2^n) Ordenação eficiente = O(n * log n) -> Teta(n * log n)