Analise complexidade de algoritmos

ETAPA 1
Passo 2
Omega: Defini-se em medir o menor tempo de execução de um algoritmo para uma entrada de tamanho n , sendo pouco usado . A analise assume que o numero procurado seria o primeiro da lista .
Theta: Defini-se por obter a média dos tempos de execução de todas as entradas de tamanho n, ou baseado em probabilidade de determinada condição ocorrer em média será necessário visitar n/2 elementos do vetor até encontrar o elemento procurado, sendo mais difícil de se determinar .
Omicron: Defini-se em obter o maior tempo de execução sobre todas as entradas de tamanho n , sendo considerado o método mais fácil de se obter , no pior dos casos será necessário visitar todos os n elementos do vetor até encontrar o elemento procurado, sendo o piro caso.
Passo 3 1- A comparação da função linear com a função quadrática pode ser representada pelo grafico a seguir :

Como podemos ver no gráfico , na função quadrática referente a tempo de processamento em função de números de entradas ele gasta muito mais tempo que uma função linear , que no qual leva o mesmo tempo que o numero de entradas (n).
Um exemplo seria que se na função linear se n varia de 0 a 10, f(n) varia de 0 a 10 , já na quadrática se n varia de 0 a 10 , f(n) varia de 0 a 200.
Para provar que o f(n) é omicron podemos definir que f(n) tem limite assintótico superior O(g(x)) ou seja , existe uma constante positiva c1 e n2 tais que 0< f(x) ≤ f(x) ≤ c1 g(x) para n ≥ n0
Resumindo a função de f(n) é sempre menor do que a função g(x) multiplicada por uma constante. 2- A diferença entre o exponencial e a cúbica é que a cúbica representado por O(n³), são uteis apenas para resolver pequenos problemas sendo que quando n é 100 o numero de operações é da ordem de 1 milhão.
O exponencial por sua vez representado por O(2n), não são uteis sob o ponto de vista prático , sendo que quando n é 20 o tempo de execução é cerca de 1 milhão.

Passo 4:
O nosso algoritmo tem a funcionalidade