Analise e complexidade de algoritmo etapa 1 passo 2

ETAPA 1 PASSO 2 MEDIDAS DE COMPLEXIDADES
ÔMEGA: E o melhor caso de medida de complexidade, ela tem o menor tempo de execução , resolve o problema para a melhor entrada n, e é difícil de ser encontrado .O termo ômega possui o significado de “fim” quando utilizado associado à primeira letra do alfabeto grego “alfa”, por exemplo, na expressão “alfa e ômega”, que representa “princípio e fim”.

OMICRON: É o caso médio, este caso tem um tempo médio de execução, se todas as entradas do mesmo tamanho são consideradas terem a mesma probabilidade de aparecer, a complexidade do caso médio pode ser definida com relação à distribuição uniforme sobre todas as entradas de tamanho n.

THETA: É o pior caso de medida de complexidade, esta medida tem o pior tempo de execução, esta é a complexidade de resolver o problema para a pior entrada de tamanho n.

PASSO 3
Seja f uma função de complexidade tal que f(n) é o número de registros consultados no arquivo (número de vezes que a chave de consulta é comparada com a chave de cada registro).
• melhor caso:
 registro procurado é o primeiro consultado
 f(n) = 1
• pior caso:
 registro procurado é o último consultado ou não está presente no arquivo;
 f(n) = n
• caso médio:
 No estudo do caso médio, vamos considerar que toda pesquisa recupera um registro. Se pi for a probabilidade de que o i-ésimo registro seja procurado, e considerando que para recuperar o i-ésimo registro são necessárias i comparações, então: f(n) = 1 x p1 + 2 x p2 + 3 x p3 + ... + n x