Tarea 3. Fecha de entrega miércoles 22 de septiembre de 2021

1. Correctitud de la regla de Horner

La regla de Horner para evaluar un polinomio es

P(x) = sum_{k=0}^n  a_k x^k

     = a0 + x( a1 + x( a2 + ... + x( a_{n-1} + x an) ...) ),

dados los coeficientes a0, a1, ..., an y un valor para x.

Un pseudocódigo para implementar la regla de Horner es:

1 y = 0
2 i = n
3 while i >= 0
4   y = ai + x * y
5   i -= 1

a) En términos de la notación Theta, ¿cuál es el tiempo de
  ejecución de este fragmento de código para la regla de Horner?

b) Escriba un pseudocódigo para implementar la evaluación 
  ingenua del polinomio que calcula cada uno de sus términos.
  ¿Cuál es el tiempo de ejecución de este algoritmo?
  ¿Cómo se compara con la regla de Horner?

c) Considere el siguiente invariante de ciclo:

  Al inicio de cada iteración del ciclo while de las líneas 3-5,

  y = sum_{k=0}^{n-(i+1)} a_{k+i+1} x^k

 interprete una suma sin términos como igual a 0. Siguiendo la
 estructura del invariante de ciclo úsela para demostrar que en
 su terminación

   y = sum_{k=0}^n a_k x^k


2. Comportamiento asintótico de polinomios

   Sea

    p(n) = sum_{i=0}^d a_i n^i,

  donde a_d > 0, y es un polinomio de grado d en n, y sea k una constante.
  Use las siguientes definiciones de la notación asintótica para probar
  las siguientes propiedades.

  a) Si k>=d, entonces p(n) = O(n^k)
  b) Si k<=d, entonces p(n) = Omega(n^k)
  c) Si k=d, entonces p(n) = Theta(n^k)
  d) Si k>d, entonces p(n) = o(n^k)
  e) Si k<d, entonces p(n) = omega(n^k)