Complexidade de pior caso
Na Ciência da computação a “Complexidade de pior caso” mede os recursos que um algoritmo precisa no pior caso. Isto dá um limitante superior dos recursos necessários ao algoritmo.
Como normalmente estamos interessados na dependência da ‘complexidade de tempo’ sobre entradas de comprimentos diferentes, abusando de terminologia, a complexidade de tempo é, algumas vezes, uma referência ao mapeamento TA:'N→’N, definido por TA(n):= maxx∈{0, 1}n{tA(x)}. Definições similares podem ser dadas para complexidade de espaço, complexidade de aleatoriedade, etc.
Considere executar o insertion sort sobre “n" números numa ram. O melhor caso para o algoritmo é quando os números já estão ordenados, o que leva O(n) passos para executar a tarefa. Entretanto, a entrada no pior caso para o algoritmo é quando os números estão na ordem reversa, e leva O(n2) passos para ordená-los; portanto a complexidade de pior caso do insertion sort é O(n2).
