Tarea 1 - Analisis de Algoritmos

ANÁLISIS DE ALGORITMOS

CB-102

TAREA # 1

Fecha de entrega: Lunes 23

1. Supón que usamos el siguiente algoritmo para evaluar el polinomio

p(x) = an xn + an-1 xn-1 + … + a1 x + a0.

        p := a0 ;

        xpower := 1;

        for i := 1, to n do

                xpower := x * xpower ;

                p:= p+ ai * power ;

        end

1. ¿Cuántas multiplicaciones se efectúan en el peor de los casos?

R=2n multiplicaciones.

2. ¿Cuántas multiplicaciones se efectúan en promedio?

R=2n multiplicaciones.

1. ¿Se puede mejorar este algoritmo?

R= Probablemente factorizando el polinomio.

1. Sea , p(n) = ak nk + ak-1 nk-1 + … + a1 n + a0 un polinomio en n de grado k con ak > 0. Prueba que p(n) está en Θ(nk).

R=

[pic 2]

Por lo tanto P(n) esta en Θ([pic 3]).

1. Sean α y β dos números reales tales que 0 < α < β . Prueba que nα está en O(nβ), pero . nβ no está en O(nα).

• [pic 4]    [pic 5]

[pic 6]

Por lo tanto Si esta acotado.

• [pic 7]    [pic 8]

[pic 9]

Por lo tanto No esta acotado.

1. Para cada una de las expresiones (A,B) de la tabla de abajo, indica si A es O, Ω, ó bien Θ de B. Asume que k, m, y n son enteros positivos, ε > 0 y c > 1 son constantes. Debes de esrcibir en cada una de las casillas sólo SI o NO. Entrega en una hoja aparte la justificación de tus respuestas.

...