Melhor caso, pior caso e caso médio

O termo desempenho do melhor caso é usado na ciência da computação para descrever um comportamento de um algoritmo sob condições ideais. Por exemplo, o melhor caso para uma simples pesquisa linear em uma lista ocorre quando o elemento desejado é o primeiro elemento da lista. O desenvolvimento e a escolha de algoritmos raramente é baseado no desempenho do melhor caso, a maioria dos acadêmicos e empresas comerciais estão mais interessados em melhorar a complexidade do caso médio e desempenho do pior caso. Algoritmos também podem ser trivialmente modificados para ter um bom desempenho no melhor caso em tempo de execução, codificando soluções para um conjunto finito de entradas, fazendo com que a medida se torne quase que insignificante.

A análise do desempenho do pior caso e caso médio têm algumas semelhanças, mas na prática, geralmente, requerem diferentes ferramentas e abordagens. Determinar o que significa a entrada média é difícil, e muitas vezes a entrada média tem propriedades que tornam difícil caracteriza-la matematicamente (considere, por exemplo, os algoritmos que são projetados para operar em cadeias de caracteres de um texto). Da mesma forma, mesmo quando uma descrição apropriada de um determinado "caso médio" (que provavelmente só será aplicável para alguns usos do algoritmo) é possível, eles tendem a resultar em análises de equações mais difíceis. A análise do pior caso tem problemas semelhantes: é normalmente impossível determinar o exato cenário de um pior caso. Em vez disso, considera-se um cenário de tal forma que ele seja no mínimo tão ruim quanto o pior caso. Por exemplo, ao analisar um algoritmo, pode-se encontrar o maior caminho possível utilizando o algoritmo (considerando o número máximo de ciclos, por exemplo), mesmo que não seja possível determinar a exata entrada que geraria esse caminho (na verdade essa entrada pode nem existir). Isso dá uma segurança na análise (pior caso nunca é subestimado), mas ela pode ser pessimista, pois pode não existir uma entrada que exija esse caminho.

Muitos problemas com mau desempenho no pior caso tem bom desempenho no caso médio. Para os problemas que queremos resolver, isso é uma coisa boa: nós podemos esperar que os casos particulares com os quais nos preocupamos sejam casos médios. Para criptografia, isso é muito ruim: nós queremos que casos típicos de um problema de criptografia sejam difíceis. Métodos como reduções aleatórias próprias podem ser usados em problemas específicos para mostrar que o pior caso não é mais difícil do que o caso médio, ou, equivalentemente, que o caso médio não é mais fácil do que o pior caso. Por outro lado, alguns algoritmos, como o da tabela hash tem poucos comportamentos de pior caso. Porém uma tabela hash bem escrita, de tamanho grande o suficiente nunca irá, estatisticamente, dar um pior caso; o número médio de operações executadas segue uma curva de decaimento exponencial e, portanto, o tempo de execução de uma operação é estatisticamente limitado.