Analisando Algoritmos
Suposições
- um único processador genérico, máquina de acesso aleatório
- tempo de execução (outros: memória, comunicação, etc)
Tempo de Execução no Pior Caso: o tempo mais longo para qualquer entrada de tamanho n
- limite superior sobre o tempo de execução para qualquer entrada
- em alguns casos como pesquisa, este é próximo
Comportamento no Caso Médio: o desempenho médio esperado sobre todas as entradas possíveis
- Este geralmente é melhor que o comportamento no pior caso
- algumas vezes este é quase igual ao pior caso