Problema 1: Calcule el tiempo utilizado por el siguiente algoritmo:

int elevado(x,n){
    /* caso base */
    if (n == 0) {
        return 1;
    }
    /* caso recursivo impar*/
    else (n es impar) {
        return x * elevado(x,n-1);
    }
    /* caso recursivo par*/
    else (n es par) {
        return elevado(x*x,n/2);
    }
}

Con esta información:

f(1) = 1

Caso impar:
f(n) = f(n-1) + 1
     = (f(n-2) + 1) + 1
     = f(n-2) + 2
     = ...
     = f(1) + n - 1
     = 1    + n - 1
f(n) = n

Caso par:
f(n) = f(n/2) + 1 = f(n/2¹) + 1
     = (f(n/4) + 1) + 1 = f(n/4) + 2 = f(n/2²) + 2
     = (f(n/8) + 1) + 2 = f(n/8) + 3 = f(n/2³) + 3
     = ...
     = f(n/2^k) + k

suponiendo: n = 2^k => k = log₂n

f(n) = f(2^k/2^k) + k = f(1) + k = 1 + k
f(n) = 1 + k = 1 + log₂n

f(n) = 1 + log₂n

La pregunta es ¿cuántas veces se repite el caso impar?
Respuesta la misma cantidad de veces que se repite el caso par

luego el n en el caso impar es en realidad log₂n por lo que el resultado final considerando los casos pares e impares es:

f(n) = 2 + 2*log₂n = O(log₂n)
 

Problema 2: Calcule el tiempo utilizado por el siguiente algoritmo:

int sumaLista (lista l){
    if l.largo = 0
        return 0
    else l.largo = 1
        return l.primerElemento
    else sumaLista (l.mitadDerecha) + sumaLista (l.mitadIzquierda);
}

Supuestos:

• el cálculo de l.mitadDerecha y l.mitadIzquierda es de costo 1
• el cálculo de encontrar el primer elemento es de costo 1

f(0) = 1
f(1) = 1

Caso recursivo:
f(n) = 2*f(n/2) + 1
     = 2*(2*f(n/4) + 1) + 1 = 4*f(n/4) + 3 = 2²*f(n/2²) + 2² - 1
     = 4*(2*f(n/8) + 1) + 3 = 8*f(n/8) + 7 = 2³*f(n/2³) + 2³ - 1
     = ...
f(n) = 2^k*f(n/2^k) + 2^k - 1

suponiendo : n = 2^k => k = log₂n

f(n) = 2^k*f(1) + 2^k - 1
f(n) = n + n - 1

f(n) = 2*n - 1 = O(n)

NOTA: este es otro ejemplo en donde la recursividad no sirve
 

Problema 3: Calcule el tiempo utilizado por el siguiente algoritmo:

lista Qsort(lista l){
    if l.length < 2
        return l
    else{
        pivote = l.elemDelMedio
        redistribuir los elementos de l de modo que los menores queden a la derecha del pivote y los mayores a la izquierda
        lDer= Qsort(l.derechaPivote);
        lIzq= Qsort(l.izquierdaPivote);
        return lDer.concatena(lIzq);
    }
}

Supuestos:

• encontrar el pivote tiene costo 1
• la redistribución de elementos tiene costo tamaño de la lista
• el cálculo de l.derechaPivote y l.izquierdaPivote es de costo 1.
• la concatenación de las listas es de costo unitario

T(1) = 1

No se considerarán las operaciones de costo unitario puesto que son de costo despreciable en la iteración (comparadas con el costo de redistribución en la lista)

Caso recursivo:
T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + n + n = 2²*f(n/2²) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + n + 2*n = 2³*T(n/2³) + 3*n
     = ...
f(n) = 2^k*T(n/2^k) + k*n

suponiendo : n = 2^k => k = log₂n

f(n) = n*T(1) + n*log₂n
f(n) = n + n*log₂n = O(n*log₂n)
 

Problema 4: Resuelva la ecuación de recurrencia f_n = 3f_n-1 - 2f_n-2 mediante:

f₀ = 0
f₁ = 1

a. Planteando el polinomio característico
b. Adivinando la serie, y demostrando su validez

a. Polinomio característico

f_n - 3f_n-1 + 2f_n-2 = 0

Suponiendo solución exponencial (f_n ~ xⁿ)

xⁿ - 3x^n-1 + 2x^n-2 = 0 / · x^2-n

x² - 3x + 2 = 0

resolviendo el polinomio cuadrático

=> x₁ = 2, x₂ = 1

Proponiendo la solución de la forma:

f_n = C₁x₁ⁿ + C₂x₂ⁿ

Con esta información, ya se puede decir que la solución es O(2ⁿ).
Hay que encontrar el valor de las constantes C₁ y C₂

f₀ = C₁x₁⁰ + C₂x₂⁰ = 0
f₁ = C₁x₁¹ + C₂x₂¹ = 1

Evaluando:

f₀ =  C₁ +  C₂ = 0
f₁ = 2C₁ +  C₂ = 1

Resolviendo el sistema matricial de 2 x 2

C₁ = 1,  C₂ = -1

=> f_n = C₁x₁ⁿ - C₂x₂ⁿ = 1*2ⁿ - 1*1ⁿ = 2ⁿ - 1

=> f_n = 2ⁿ - 1 = O(2ⁿ)

b) Adivinando la serie, y demostrándola

f₀ = 0
f₁ = 1
f₂ = 3
f₃ = 7

=> f_n = 2ⁿ - 1

Lo interesante es demostrar esto :)

Dado:
f_n = 2ⁿ - 1
f_n-1 = 2^n-1 - 1

Demostrar que: f_n+1 = 2ⁿ⁺¹ - 1

f_n+1 = 3f_n - 2f_n-1
f_n+1 = 3*(2ⁿ - 1) - 2(2^n-1 - 1)
f_n+1 = 3*2ⁿ - 3 - 2*2^n-1 + 2
f_n+1 = 3*2ⁿ - 2ⁿ -1
f_n+1 = 2*2ⁿ -1

=> f_n+1 = 2ⁿ⁺¹ -1, con lo que se obtiene que f_n = O(2ⁿ)

QED (queda esto demostrado)
 

Problema 5: Resuelva la ecuación de recurrencia f_n = f_n-1 - f_n-2 planteando su polinomio característico.

f₀ = 0
f₁ = 1

f_n - f_n-1 + f_n-2 = 0

Suponiendo solución exponencial (f_n ~ xⁿ)

xⁿ - x^n-1 + x^n-2 = 0 / · x^2-n

x² - x + 1 = 0

resolviendo el polinomio cuadrático

=> 

en coordenadas polares:

Proponiendo la solución de la forma:

f_n = C₁x₁ⁿ + C₂x₂ⁿ

Con esta información, ya se puede decir que la solución es O(1), en realidad gira torno al circulo unitario.
Hay que encontrar el valor de las constantes C₁ y C₂

f₀ = C₁x₁⁰ + C₂x₂⁰ = 0
f₁ = C₁x₁¹ + C₂x₂¹ = 1

Evaluando:

f₀ = C₁         + C₂         = 0

Resolviendo el sistema matricial de 2 x 2

=> f_n = C₁x₁ⁿ - C₂x₂ⁿ

en coordenadas polares:

utilizando e^jt = cos(t) + j*sen(t):

recordando que coseno es función par, seno es función impar y reduciendo los términos:

Notar que a pesar de que pasamos por números complejos, y que se usaron funciones trigonométricas, los resultados de la serie son todos enteros !!
 

Problema 6: Resuelva la ecuación de recurrencia T(n) = 2T(n/2) - 3T(n/4) + 7

T(1) = 1
T(2) = 2

Hint: realice un cambio de variables, elimine el término constante y resuelva el polinomio característico.

Cambio de variables: n = 2^k, luego H(k) = T(2^k) = T(n)

también cambian las condiciones de inicio:

H(0) = 1
H(1) = 2

Con esto tenemos:

(1) H(k)   = 2H(k-1) - 3H(k-2) + 7

Para eliminar el término constante, consideremos H(n-1)

(2) H(k-1) = 2H(k-2) - 3H(k-3) + 7

Calculando (1) - (2)

H(k) - 3H(k-1) + 5H(k-2) - 3H(k-3) = 0

Suponiendo solución exponencial (H(k) ~ xⁿ)

x^k - 3x^k-1 + 5x^k-2 - 3x^k-3 = 0 / · x^3-k
x³ - 3x² + 5x - 3 = 0

las raíces del polinomio son: