Page 30 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Algoritmo 1.4. Evaluación de un polinomio P(x) en forma iterativa

Como medida del tamaño tomaremos para N el grado del polinomio, que es el número de coeficien-
tes. Así pues, el bucle más exterior se ejecuta N veces. El bucle interior se emplea para elevar a X la
potencia indicada por la variable i, respectivamente. Por lo que:

C = (n – 1) + (n – 2) +... + 2 + 1

Ahora bien, utilizando el truco de Gauss para la suma de números naturales se tiene:

2S = n*(n + 1), por lo tanto, S = n* (n + 1) /2
n n

24