Analise o custo computacional dos algoritmos a seguir, que c...

Analise o custo computacional dos algoritmos a seguir, que calculam o valor do polinômio de grau n na forma P(x) = a_n*x^n + a_(n-1)x^(n-1) + ... + a_1x + a_0 onde os coeficientes são números de ponto flutuante armazenados no vetor [a_0, ..., a_n], e o coeficiente a_n é diferente de zero. Todos os coeficientes podem assumir qualquer valor, exceto o coeficiente a_n que é diferente de zero.

ALGORITMO 1:

soma = a[0] repita para i=1 até n se a[i] <> 0.0 então potencia = x repita para j = 2 até i potencia = potencia * x fim repita soma = soma + a[i] fim se fim repita imprima(soma)

ALGORITMO 2:

soma = a[n] repita para i = n-1 até 0 passo -1 soma = soma * x + a[i] fim repita imprima(soma)

Com bases nos algoritmos 1 e 2, avalie as assertivas a seguir e a relação proposta entre elas.

Os algoritmos possuem a mesma complexidade assintótica

PORQUE

1 Para o melhor caso, ambos possuem complexidade O(n)

A respeito dessas assertivas, ambas estão corretas.