Ejercicios resueltos de análisis de complejidad algorítmica

1. Bucles sencillos

Ejercicio 1

function ejercicio1(int n)
    for (int i = 0; i < n; i += 3)          // Línea 1
        print(i)                            // Línea 2
    end_for                                 // Línea 3
    return n                                // Línea 4
end_function

1.1 Cálculo del

El tiempo de ejecución de la función viene dado por la suma del tiempo de ejecución del bucle y el tiempo de ejecución de la operación de retorno:

$T(n) = T_{bucle}(n) + T_{return}(n)$

Donde:

es el tiempo de ejecución del bucle (líneas 1-3).
es el tiempo de ejecución de la línea 4.

Como , donde es el tiempo constante de la operación de retorno:

$T(n) = T_{bucle}(n) + c_1$

Para calcular vamos a reescribir el bucle de la siguiente manera:

    for (int i = 0; i <= n - 1; i += 3)      // Línea 1
        print(i)                             // Línea 2
    end_for                                  // Línea 3

Hemos reescrito la condición original como para identificar el límite superior del intervalo, lo que simplifica la construcción del sumatorio.

Para determinar el número de iteraciones del bucle (líneas 1-3), analizamos la progresión de los valores que toma la variable :

Límite inferior:
Límite superior:
Incremento: 3 en cada paso ()

Dado que el bucle no se incrementa de 1 en 1, calculamos el número total de iteraciones aplicando la fórmula de los términos de una progresión aritmética:

$\text{Número de iteraciones} = \frac{\text{Límite superior} - \text{Límite inferior}}{\text{Incremento}} + 1$

Sustituyendo los valores de nuestro bucle:

$\text{Número de iteraciones} = \frac{(n - 1) - 0}{3} + 1$

Podemos expresar el tiempo de ejecución del bucle como un sumatorio donde el índice recorre desde la primera hasta la última iteración:

$T_{bucle}(n) = \sum_{i=1}^{\lfloor \frac{n - 1}{3} + 1 \rfloor} c_2$

Donde es el tiempo constante de las operaciones dentro del bucle. Resolviendo el sumatorio obtenemos:

$T_{bucle}(n) \leq c_2 \cdot \left( \frac{n - 1}{3} + 1 \right)$

Simplificando los términos de la expresión:

$T_{bucle}(n) \leq c_2 \cdot \left( \frac{n}{3} - \frac{1}{3} + 1 \right) = \frac{c_2}{3}n + \frac{2{c_2}}{3}$

Sustituyendo en la expresión original:

$T(n) = T_{bucle}(n) + c_1 = \frac{c_2}{3}n + \frac{2{c_2}}{3} + c_1$

1.2 Cálculo del orden de complejidad

En el análisis asintótico, despreciamos las constantes multiplicativas y los términos de menor orden:

El término de mayor orden es .
Las constantes , y no afectan al crecimiento asintótico.

El algoritmo tiene una complejidad lineal, ya que el número de operaciones crece de manera directamente proporcional a .

$T(n) \in \mathcal{O}(n)$

Ejercicio 2

function ejercicio2(int n)
    for (int i = 0; i < n/2; i += 5)        // Línea 1
        print(i)                            // Línea 2
    end_for                                 // Línea 3
    return n                                // Línea 4
end_function

2.1 Cálculo del

El tiempo de ejecución de la función viene dado por la suma del tiempo de ejecución del bucle y el tiempo de ejecución de la operación de retorno:

$T(n) = T_{bucle}(n) + T_{return}(n)$

Donde:

es el tiempo de ejecución del bucle (líneas 1-3).
es el tiempo de ejecución de la línea 4.

Como , donde es el tiempo constante de la operación de retorno:

$T(n) = T_{bucle}(n) + c_1$

Para calcular vamos a reescribir el bucle de la siguiente manera:

    for (int i = 0; i <= (n/2) - 1; i += 5)  // Línea 1
        print(i)                             // Línea 2
    end_for                                  // Línea 3

Hemos reescrito la condición original como para identificar el límite superior del intervalo, lo que simplifica la construcción del sumatorio.

Para determinar el número de iteraciones del bucle (líneas 1-3), analizamos la progresión de los valores que toma la variable :

Límite inferior:
Límite superior:
Incremento: 5 en cada paso ()

Dado que el bucle no se incrementa de 1 en 1, calculamos el número total de iteraciones aplicando la fórmula de los términos de una progresión aritmética:

$\text{Número de iteraciones} = \frac{\text{Límite superior} - \text{Límite inferior}}{\text{Incremento}} + 1$

Sustituyendo los valores de nuestro bucle:

$\text{Número de iteraciones} = \frac{(n/2 - 1) - 0}{5} + 1$

Podemos expresar el tiempo de ejecución del bucle como un sumatorio donde el índice recorre desde la primera hasta la última iteración:

$T_{bucle}(n) = \sum_{i=1}^{\lfloor \frac{n/2 - 1}{5} + 1 \rfloor} c_2$

Donde es el tiempo constante de las operaciones dentro del bucle. Resolviendo el sumatorio obtenemos:

$T_{bucle}(n) \leq c_2 \cdot \left( \frac{n/2 - 1}{5} + 1 \right)$

Simplificando los términos de la expresión:

$T_{bucle}(n) \leq c_2 \cdot \left( \frac{n}{10} - \frac{1}{5} + 1 \right) = \frac{c_2}{10}n + \frac{4{c_2}}{5}$

Sustituyendo en la expresión original:

$T(n) = T_{bucle}(n) + c_1 = \frac{c_2}{10}n + \frac{4{c_2}}{5} + c_1$

2.2 Cálculo del orden de complejidad

En el análisis asintótico, despreciamos las constantes multiplicativas y los términos de menor orden:

El término de mayor orden es .
Las constantes , y no afectan al crecimiento asintótico.

El algoritmo tiene una complejidad lineal, ya que el número de operaciones crece de manera directamente proporcional a .

$T(n) \in \mathcal{O}(n)$

Ejercicio 3

function ejercicio3(int n)
    for (int i = n; i > 0; i--)             // Línea 1
        print(i)                            // Línea 2
    end_for                                 // Línea 3
    return n                                // Línea 4
end_function

3.1 Cálculo del

El tiempo de ejecución de la función viene dado por la suma del tiempo de ejecución del bucle y el tiempo de ejecución de la operación de retorno:

$T(n) = T_{bucle}(n) + T_{return}(n)$

Donde:

es el tiempo de ejecución del bucle (líneas 1-3).
es el tiempo de ejecución de la línea 4.

Como , donde es el tiempo constante de la operación de retorno:

$T(n) = T_{bucle}(n) + c_1$

Para determinar el número de iteraciones del bucle (líneas 1-3), analizamos la progresión de los valores que toma la variable :

Valor inicial:
Condición:
Decremento: 1 en cada paso ()

La lógica en bucles con decremento es idéntica a la de los bucles con incremento. La siguiente fórmula nos permite calcular el número de iteraciones basándonos en los límites del intervalo:

$\text{Número de iteraciones} = \frac{\text{Límite superior (inicio)} - \text{Límite inferior (fin)}}{\text{Decremento}} + 1$

Sustituyendo los valores de nuestro bucle:

$\text{Iteraciones} = \frac{n - 1}{1} + 1 = n$

Podemos expresar el tiempo de ejecución del bucle como un sumatorio donde el índice recorre desde la primera hasta la última iteración:

$T_{bucle}(n) = \sum_{i=1}^{n} c_2$

Donde es el tiempo constante de las operaciones dentro del bucle. Resolviendo el sumatorio obtenemos:

$T_{bucle}(n) = n \cdot c_2$

Sustituyendo en la expresión original:

$T(n) = T_{bucle}(n) + c_1 = c_2 \cdot n + c_1$

3.2 Cálculo del orden de complejidad

Para determinar el orden de complejidad, realizamos el análisis asintótico de la expresión :

Descartamos los términos de menor orden. La constante es un término de orden inferior comparado con .
Descartamos las constantes multiplicativas. La constante no afecta al crecimiento asintótico de la función.

El término dominante es , por lo que el algoritmo tiene una complejidad lineal.

$T(n) \in \mathcal{O}(n)$

Ejercicio 4

function ejercicio4(int n)
    for (int i = 1; i <= n; i = i * 2)      // Línea 1
        print(i)                            // Línea 2
    end_for                                 // Línea 3
    return n                                // Línea 4
end_function

4.1 Cálculo del

El tiempo de ejecución de la función viene dado por la suma del tiempo de ejecución del bucle y el tiempo de ejecución de la operación de retorno:

$T(n) = T_{bucle}(n) + T_{return}(n)$

Donde:

es el tiempo de ejecución del bucle (líneas 1-3).
es el tiempo de ejecución de la línea 4.

Como , donde es el tiempo constante de la operación de retorno:

$T(n) = T_{bucle}(n) + c_1$

Para determinar el número de iteraciones del bucle (líneas 1-3), analizamos la progresión geométrica de los valores que toma la variable :

Iteración 0:
Iteración 1:
Iteración 2:
…
Iteración k:

El bucle continúa mientras se cumpla la condición . Para despejar el número de iteraciones en la última vuelta (), resolvemos la siguiente inecuación:

$\begin{aligned} &2^k \le n \\ &\log_2(2^k) \le \log_2(n) \\ &k \le \log_2 n \end{aligned}$

Por las propiedades de los logaritmos .

El número total de iteraciones es , contando desde la primera iteración hasta la última .

Podemos expresar el tiempo de ejecución del bucle como un sumatorio donde el índice representa cada iteración:

$T_{bucle}(n) = \sum_{k=0}^{\lfloor \log_2 n \rfloor} c_2$

Donde es el tiempo constante de las operaciones dentro del bucle. Resolviendo el sumatorio obtenemos:

$T_{bucle}(n) = c_2 \cdot (\lfloor \log_2 n \rfloor + 1)$

Sustituyendo en la expresión original:

$T(n) = T_{bucle}(n) + c_1 = c_2 \cdot (\lfloor \log_2 n \rfloor + 1) + c_1$

4.2 Cálculo del orden de complejidad

Para determinar el orden de complejidad, realizamos el análisis asintótico:

Descartamos los términos de menor orden. Las constantes y son términos de orden inferior comparados con .
Descartamos las constantes multiplicativas. Las constantes no afectan al crecimiento asintótico.
Cambio de base del logaritmo. Todas las funciones logarítmicas pertenecen al mismo orden de complejidad, independientemente de la base.

El término dominante es , por lo que el algoritmo tiene una complejidad logarítmica.

$T(n) \in \mathcal{O}(\log n)$

Ejercicio 5

function ejercicio5(int n)
    for (int i = n; i >= 1; i = i / 2)      // Línea 1
        print(i)                            // Línea 2
    end_for                                 // Línea 3
    return n                                // Línea 4
end_function

5.1 Cálculo del

El tiempo de ejecución de la función viene dado por la suma del tiempo de ejecución del bucle y el tiempo de ejecución de la operación de retorno:

$T(n) = T_{bucle}(n) + T_{return}(n)$

Donde:

es el tiempo de ejecución del bucle (líneas 1-3).
es el tiempo de ejecución de la línea 4.

Como , donde es el tiempo constante de la operación de retorno:

$T(n) = T_{bucle}(n) + c_1$

Para determinar el número de iteraciones del bucle (líneas 1-3), analizamos la progresión geométrica decreciente de los valores que toma la variable :

Iteración 0:
Iteración 1:
Iteración 2:
…
Iteración k:

El bucle continúa mientras se cumpla la condición . Para despejar el número de iteraciones en la última vuelta (), resolvemos la siguiente inecuación:

$\begin{aligned} &\frac{n}{2^k} \ge 1 \\ &n \ge 2^k \\ &\log_2(n) \ge \log_2(2^k) \\ &\log_2 n \ge k \end{aligned}$

Por las propiedades de los logaritmos .

El número total de iteraciones es , contando desde la primera iteración hasta la última .

Podemos expresar el tiempo de ejecución del bucle como un sumatorio donde el índice representa cada iteración:

$T_{bucle}(n) = \sum_{k=0}^{\lfloor \log_2 n \rfloor} c_2$

Donde es el tiempo constante de las operaciones dentro del bucle. Resolviendo el sumatorio obtenemos:

$T_{bucle}(n) = c_2 \cdot (\lfloor \log_2 n \rfloor + 1)$

Sustituyendo en la expresión original:

$T(n) = T_{bucle}(n) + c_1 = c_2 \cdot (\lfloor \log_2 n \rfloor + 1) + c_1$

5.2 Cálculo del orden de complejidad

Para determinar el orden de complejidad, realizamos el análisis asintótico:

Descartamos los términos de menor orden. Las constantes y son términos de orden inferior comparados con .
Descartamos las constantes multiplicativas. Las constantes no afectan al crecimiento asintótico.
Cambio de base del logaritmo. Todas las funciones logarítmicas pertenecen al mismo orden de complejidad, independientemente de la base.

El término dominante es , por lo que el algoritmo tiene una complejidad logarítmica.

$T(n) \in \mathcal{O}(\log n)$

Ejercicio 6

function ejercicio6(int n)
    for (int i = 1; i <= n; i = i * 3)      // Línea 1
        print(i)                            // Línea 2
    end_for                                 // Línea 3
    return n                                // Línea 4
end_function

6.1 Cálculo del

El tiempo de ejecución de la función viene dado por la suma del tiempo de ejecución del bucle y el tiempo de ejecución de la operación de retorno:

$T(n) = T_{bucle}(n) + T_{return}(n)$

Donde:

es el tiempo de ejecución del bucle (líneas 1-3).
es el tiempo de ejecución de la línea 4.

Como , donde es el tiempo constante de la operación de retorno:

$T(n) = T_{bucle}(n) + c_1$

Para determinar el número de iteraciones del bucle (líneas 1-3), analizamos la progresión geométrica de los valores que toma la variable :

Iteración 0:
Iteración 1:
Iteración 2:
…
Iteración k:

El bucle continúa mientras se cumpla la condición . Para despejar el número de iteraciones en la última vuelta (), resolvemos la siguiente inecuación:

$\begin{aligned} &3^k \le n \\ &\log_3(3^k) \le \log_3(n) \\ &k \le \log_3 n \end{aligned}$

Por las propiedades de los logaritmos .

El número total de iteraciones es , contando desde la primera iteración hasta la última .

Podemos expresar el tiempo de ejecución del bucle como un sumatorio donde el índice representa cada iteración:

$T_{bucle}(n) = \sum_{k=0}^{\lfloor \log_3 n \rfloor} c_2$

Donde es el tiempo constante de las operaciones dentro del bucle. Resolviendo el sumatorio obtenemos:

$T_{bucle}(n) = c_2 \cdot (\lfloor \log_3 n \rfloor + 1)$

Sustituyendo en la expresión original:

$T(n) = T_{bucle}(n) + c_1 = c_2 \cdot (\lfloor \log_3 n \rfloor + 1) + c_1$

6.2 Cálculo del orden de complejidad

Para determinar el orden de complejidad, realizamos el análisis asintótico:

Descartamos los términos de menor orden. Las constantes y son términos de orden inferior comparados con .
Descartamos las constantes multiplicativas. Las constantes no afectan al crecimiento asintótico.
Cambio de base del logaritmo. Todas las funciones logarítmicas pertenecen al mismo orden de complejidad, independientemente de la base (recordemos que , siendo una constante).

El término dominante es , por lo que el algoritmo tiene una complejidad logarítmica.

$T(n) \in \mathcal{O}(\log n)$

2. Bucles anidados independientes

Ejercicio 7

function ejercicio7(int n)
    for (int i = 0; i < n/2; i++)           // Línea 1
        for(int j = 0; j < n/2; j++)        // Línea 2
            print(i + j)                    // Línea 3
        end_for                             // Línea 4
    end_for                                 // Línea 5
    return n                                // Línea 6
end_function

7.1 Cálculo del

El tiempo de ejecución de la función viene dado por la suma del tiempo de ejecución del bucle anidado y el tiempo de ejecución de la operación de retorno:

$T(n) = T_{bucle}(n) + T_{return}(n)$

Como , la expresión es:

$T(n) = T_{bucle}(n) + c_1$

Para calcular , analizamos la estructura anidada. El tiempo total es la suma de las ejecuciones del bucle interno multiplicada por las iteraciones del bucle externo.

Para determinar el número de iteraciones de ambos bucles:

Bucle externo (i): Va de a . El número de iteraciones es .
Bucle interno (j): Va de a . El número de iteraciones es .

Podemos expresar el tiempo de ejecución total como un sumatorio anidado:

$T_{bucle}(n) = \sum_{i=1}^{\lfloor n/2 \rfloor} \sum_{j=1}^{\lfloor n/2 \rfloor} c_2$

Donde es el tiempo constante de la operación dentro del bucle interno. Resolviendo el sumatorio interno:

$\sum_{j=1}^{\lfloor n/2 \rfloor} c_2 = \lfloor n/2 \rfloor \cdot c_2$

Sustituyendo en el sumatorio externo:

$T_{bucle}(n) = \sum_{i=1}^{\lfloor n/2 \rfloor} (\lfloor n/2 \rfloor \cdot c_2) = \lfloor n/2 \rfloor \cdot \lfloor n/2 \rfloor \cdot c_2 \approx \frac{n^2}{4} c_2$

Sustituyendo en la expresión original:

$T(n) = \frac{c_2}{4}n^2 + c_1$

7.2 Cálculo del orden de complejidad

Para determinar el orden de complejidad, realizamos el análisis asintótico:

Descartamos los términos de menor orden. La constante es de orden inferior frente a .
Descartamos las constantes multiplicativas. El factor no afecta al crecimiento asintótico.

El término dominante es , por lo que el algoritmo tiene una complejidad cuadrática.

$T(n) \in \mathcal{O}(n^2)$

Ejercicio 8

function ejercicio8(int n)
    int m = 3000                            // Línea 1
    for (int i = 0; i < n/2; i++)           // Línea 2
        for(int j = 0; j < m * 1000; j++)   // Línea 3
            print(i + j + m)                // Línea 4
        end_for                             // Línea 5
    end_for                                 // Línea 6
    return n                                // Línea 7
end_function

8.1 Cálculo del

El tiempo de ejecución de la función viene dado por la suma del tiempo de ejecución de la inicialización, el bucle anidado y el retorno:

$T(n) = T_{init}(n) + T_{bucle}(n) + T_{return}(n)$

Donde y . La expresión se simplifica a:

$T(n) = c_0 + T_{bucle}(n) + c_1$

Para calcular , analizamos las iteraciones de cada bucle:

Bucle externo (i): Va de a . El número de iteraciones es .
Bucle interno (j): Va de a . Como , el número de iteraciones es .

Es muy importante observar que el número de iteraciones del bucle interno no depende de . Por tanto, el tiempo de ejecución del bucle interno es una constante .

Podemos expresar el tiempo de ejecución del bucle total como:

$T_{bucle}(n) = \sum_{i=1}^{\lfloor n/2 \rfloor} C = \lfloor n/2 \rfloor \cdot C$

Sustituyendo los valores constantes:

$T_{bucle}(n) = \lfloor n/2 \rfloor \cdot (3,000,000 \cdot c_2)$

La expresión final de es:

$T(n) = \frac{3,000,000 \cdot c_2}{2}n + (c_0 + c_1)$

8.2 Cálculo del orden de complejidad

Para determinar el orden de complejidad, realizamos el análisis asintótico:

Descartamos los términos de menor orden. La constante es despreciable frente al término que contiene .
Descartamos las constantes multiplicativas. Aunque el factor multiplicativo sea muy grande, sigue siendo una constante que no escala con el tamaño de la entrada .

El término dominante es , por lo que el algoritmo tiene una complejidad lineal.

$T(n) \in \mathcal{O}(n)$

Ejercicio 9

function ejercicio9(int n)
    int m = n / 10000                       // Línea 1
    for (int i = 0; i < n/2; i++)           // Línea 2
        for(int j = 0; j < m; j += 20)      // Línea 3
            print(i + j)                    // Línea 4
        end_for                             // Línea 5
    end_for                                 // Línea 6
    return n                                // Línea 7
end_function

9.1 Cálculo del

El tiempo de ejecución de la función viene dado por la suma del tiempo de ejecución de la inicialización, el bucle anidado y el retorno:

$T(n) = T_{init}(n) + T_{bucle}(n) + T_{return}(n)$

Donde y .

Para calcular , analizamos las iteraciones de cada bucle:

Bucle externo (i): Va de a . El número de iteraciones es .
Bucle interno (j): Va de a con incrementos de 20. Dado que , el número de iteraciones es .

Podemos expresar el tiempo de ejecución del bucle total como un sumatorio anidado:

$T_{bucle}(n) = \sum_{i=1}^{\lfloor n/2 \rfloor} \sum_{j=1}^{\lfloor \frac{n/10000 - 1}{20} + 1 \rfloor} c_2$

Resolviendo el sumatorio interno:

$\sum_{j=1}^{\lfloor \frac{n/10000 - 1}{20} + 1 \rfloor} c_2 = \left( \frac{n/10000 - 1}{20} + 1 \right) \cdot c_2$

Sustituyendo en el sumatorio externo:

$T_{bucle}(n) = \sum_{i=1}^{\lfloor n/2 \rfloor} \left( \frac{n}{200000} + 1 \right) \cdot c_2 = \lfloor n/2 \rfloor \cdot \left( \frac{n}{200000} + 1 \right) \cdot c_2 \approx \frac{n^2}{400000} c_2 + \frac{n}{2} c_2$

Sustituyendo en la expresión original de :

$T(n) \approx \frac{c_2}{400000}n^2 + \frac{c_2}{2}n + (c_0 + c_1)$

9.2 Cálculo del orden de complejidad

Para determinar el orden de complejidad, realizamos el análisis asintótico:

Descartamos los términos de menor orden. Los términos y las constantes son despreciables frente al crecimiento de .
Descartamos las constantes multiplicativas. El factor no afecta al crecimiento asintótico.

El término dominante es , por lo que el algoritmo tiene una complejidad cuadrática.

$T(n) \in \mathcal{O}(n^2)$

Ejercicio 10

function ejercicio10(int n)
    int m = n * n                           // Línea 1
    for (int i = n/2; i > 1; i = i / 3)     // Línea 2
        for(int j = 0; j < m; j++)          // Línea 3
            print(i + j)                    // Línea 4
        end_for                             // Línea 5
    end_for                                 // Línea 6
    return n                                // Línea 7
end_function

10.1 Cálculo del

El tiempo de ejecución de la función viene dado por la suma del tiempo de ejecución de la inicialización, el bucle anidado y el retorno:

$T(n) = T_{init}(n) + T_{bucle}(n) + T_{return}(n)$

Donde y . La expresión se simplifica a:

$T(n) = c_0 + T_{bucle}(n) + c_1$

Para calcular , analizamos las iteraciones de cada bucle:

Bucle externo (i): Analizamos la progresión geométrica decreciente de los valores que toma la variable , con valor inicial y dividiéndose por 3 en cada paso (). El bucle continúa mientras . Despejando el número de iteraciones en la última vuelta ():

$\begin{aligned} &\frac{n/2}{3^k} > 1 \\ &n/2 > 3^k \\ &\log_3(n/2) > k \end{aligned}$

El número de iteraciones es .

Por las propiedades de los logaritmos .

Bucle interno (j): Va de a con incrementos de 1. Como , el número de iteraciones es .

Podemos expresar el tiempo de ejecución del bucle total como un sumatorio anidado:

$T_{bucle}(n) = \sum_{k=0}^{\lfloor \log_3(n/2) \rfloor} \sum_{j=0}^{n^2-1} c_2$

Resolviendo el sumatorio interno:

$\sum_{j=0}^{n^2-1} c_2 = n^2 \cdot c_2$

Sustituyendo en el sumatorio externo:

$T_{bucle}(n) = \sum_{k=0}^{\lfloor \log_3(n/2) \rfloor} (n^2 \cdot c_2) = (\lfloor \log_3(n/2) \rfloor + 1) \cdot n^2 \cdot c_2$

Sustituyendo en la expresión original de :

$T(n) = c_2 \cdot n^2 \cdot (\lfloor \log_3(n/2) \rfloor + 1) + c_0 + c_1$

10.2 Cálculo del orden de complejidad

Para determinar el orden de complejidad, realizamos el análisis asintótico:

Descartamos los términos de menor orden. Las constantes y son despreciables frente al término dominante que incluye y el logaritmo. Además, la constante aditiva del logaritmo es de menor orden.
Descartamos las constantes multiplicativas. El factor no afecta al crecimiento asintótico.
Cambio de base y constantes en el logaritmo. Recordamos que . La resta de una constante no altera el orden asintótico, y la base del logaritmo se omite en la notación de orden de complejidad.

El término dominante es , por lo que el algoritmo tiene una complejidad cuadrática logarítmica.

$T(n) \in \mathcal{O}(n^2 \log n)$

Ejercicio 11

function ejercicio11(int n)
    int m = 2147483647; //MAX_INTEGER       // Línea 1
    for (int i = 0; i < m; i++)             // Línea 2
        for(int j = m; j < m; j = j / 2)    // Línea 3
            print(i + j)                    // Línea 4
        end_for                             // Línea 5
    end_for                                 // Línea 6
    return n                                // Línea 7
end_function

11.1 Cálculo del

El tiempo de ejecución de la función viene dado por la suma del tiempo de ejecución de la inicialización, el bucle anidado y el retorno:

$T(n) = T_{init}(n) + T_{bucle}(n) + T_{return}(n)$

Donde y . La expresión se simplifica a:

$T(n) = c_0 + T_{bucle}(n) + c_1$

Para calcular , analizamos las iteraciones de cada bucle:

Bucle interno (j): Su inicialización es j = m y su condición de continuación es j < m. Como la variable j comienza con un valor igual a m, la condición j < m es falsa desde la primera evaluación. Por lo tanto, el cuerpo del bucle interno (línea 4) no se ejecuta nunca (0 iteraciones). Sin embargo, evaluar la condición del bucle interno en cada iteración del bucle externo tiene un coste constante .
Bucle externo (i): Va de a con incrementos de 1. El número de iteraciones es exactamente . Como , este es un valor enorme, pero totalmente constante (no depende de la variable de entrada ).

El bucle externo se ejecuta veces, y en cada iteración solo se realiza la evaluación de la condición del bucle interno ().

Podemos expresar el tiempo de ejecución del bucle total como un sumatorio:

$T_{bucle}(n) = \sum_{i=0}^{m-1} c_2 = m \cdot c_2$

Sustituyendo el valor constante de :

$T_{bucle}(n) = 2147483647 \cdot c_2$

Sustituyendo en la expresión original de :

$T(n) = 2147483647 \cdot c_2 + c_0 + c_1$

11.2 Cálculo del orden de complejidad

Para determinar el orden de complejidad, realizamos el análisis asintótico:

El número de operaciones que realiza la función no depende del valor de .
Todos los términos de la expresión son valores constantes. En el análisis asintótico, toda expresión constante se agrupa y asimila a .

Dado que el algoritmo requiere el mismo tiempo de ejecución independientemente del tamaño de la entrada, tiene una complejidad constante.

$T(n) \in \mathcal{O}(1)$

3. Bucles anidados dependientes

Ejercicio 12

function ejercicio12(int n)
    for (int i = 1; i <= n; i++)            // Línea 1
        for(int j = 1; j <= i; j++)         // Línea 2
            print(i + j)                    // Línea 3
        end_for                             // Línea 4
    end_for                                 // Línea 5
    return n                                // Línea 6
end_function

12.1 Cálculo del

El tiempo de ejecución de la función viene dado por la suma del tiempo de ejecución del bucle anidado y el retorno:

$T(n) = T_{bucle}(n) + T_{return}(n)$

Como , la expresión se simplifica a:

$T(n) = T_{bucle}(n) + c_1$

Para calcular , analizamos las iteraciones de cada bucle. A diferencia de los bucles anidados independientes, en este caso el límite superior del bucle interno depende de la variable del bucle externo.

Bucle externo (i): Va de a con incrementos de 1.
Bucle interno (j): Va de a con incrementos de 1. El número de iteraciones para un valor dado de es exactamente .

Podemos expresar el tiempo de ejecución del bucle total mediante un doble sumatorio:

$T_{bucle}(n) = \sum_{i=1}^{n} \sum_{j=1}^{i} c_2$

Donde es el coste constante de las operaciones ejecutadas en el bucle interno (línea 3).

Resolvemos primero el sumatorio interno:

$\sum_{j=1}^{i} c_2 = c_2 \cdot i$

Ahora sustituimos este resultado en el sumatorio externo:

$T_{bucle}(n) = \sum_{i=1}^{n} (c_2 \cdot i) = c_2 \sum_{i=1}^{n} i$

Recordamos que la suma de los primeros números naturales (progresión aritmética) es .

Sustituyendo la fórmula anterior en la expresión del sumatorio:

$T_{bucle}(n) = c_2 \cdot \frac{n(n+1)}{2} = \frac{c_2}{2} n^2 + \frac{c_2}{2} n$

Sustituyendo en la expresión original de :

$T(n) = \frac{c_2}{2} n^2 + \frac{c_2}{2} n + c_1$

12.2 Cálculo del orden de complejidad

Para determinar el orden de complejidad, realizamos el análisis asintótico:

Descartamos los términos de menor orden. Los términos proporcionales a y las constantes () son despreciables frente al término cuadrático cuando es grande.
Descartamos las constantes multiplicativas. El factor no afecta al crecimiento asintótico de la función.

El término dominante es , por lo que el algoritmo tiene una complejidad cuadrática.

$T(n) \in \mathcal{O}(n^2)$

Ejercicio 13

function ejercicio13(int n)
    for (int i = 1; i <= n * n - 10; i++)           // Línea 1
        for(int j = 1; j <= i; j++)                 // Línea 2
            print(i + j)                            // Línea 3
        end_for                                     // Línea 4
    end_for                                         // Línea 5
    return n                                        // Línea 6
end_function

13.1 Cálculo del

El tiempo de ejecución de la función viene dado por la suma del tiempo de ejecución del bucle anidado y el retorno:

$T(n) = T_{bucle}(n) + T_{return}(n)$

Como , la expresión se simplifica a:

$T(n) = T_{bucle}(n) + c_1$

Bucle externo (i): Va de a con incrementos de 1.
Bucle interno (j): Va de a con incrementos de 1. El número de iteraciones para un valor dado de es exactamente .

Podemos expresar el tiempo de ejecución del bucle total mediante un doble sumatorio:

$T_{bucle}(n) = \sum_{i=1}^{n^2-10} \sum_{j=1}^{i} c_2$

Donde es el coste constante de las operaciones ejecutadas en el bucle interno (línea 3).

Resolvemos primero el sumatorio interno:

$\sum_{j=1}^{i} c_2 = c_2 \cdot i$

Ahora sustituimos este resultado en el sumatorio externo:

$T_{bucle}(n) = \sum_{i=1}^{n^2-10} (c_2 \cdot i) = c_2 \sum_{i=1}^{n^2-10} i$

Recordamos que la suma de los primeros números naturales (progresión aritmética) es .

Aplicando la fórmula para el límite :

$T_{bucle}(n) = c_2 \cdot \frac{(n^2-10)((n^2-10)+1)}{2} = c_2 \cdot \frac{(n^2-10)(n^2-9)}{2}$

Desarrollando el producto polinómico:

$T_{bucle}(n) = \frac{c_2}{2} (n^4 - 9n^2 - 10n^2 + 90) = \frac{c_2}{2} n^4 - \frac{19c_2}{2} n^2 + 45c_2$

Sustituyendo en la expresión original de :

$T(n) = \frac{c_2}{2} n^4 - \frac{19c_2}{2} n^2 + 45c_2 + c_1$

13.2 Cálculo del orden de complejidad

Para determinar el orden de complejidad, realizamos el análisis asintótico:

Descartamos los términos de menor orden. Los términos proporcionales a y las constantes () son despreciables frente al término polinómico de mayor grado cuando es grande.
Descartamos las constantes multiplicativas. El factor no afecta al crecimiento asintótico de la función.

El término dominante es , por lo que el algoritmo tiene una complejidad polinómica de grado 4.

$T(n) \in \mathcal{O}(n^4)$

Ejercicio 14

function ejercicio14(int n)
    for (int i = 1; i <= n; i++)                    // Línea 1
        for(int j = 1; j <= i; j++)                 // Línea 2
            for(int k = 1; k <= i; k++)             // Línea 3
                print(i + j + k)                    // Línea 4
            end_for                                 // Línea 5
        end_for                                     // Línea 6
    end_for                                         // Línea 7
    return n                                        // Línea 8
end_function

14.1 Cálculo del

El tiempo de ejecución de la función viene dado por la suma del tiempo de ejecución del bucle anidado y el retorno:

$T(n) = T_{bucle}(n) + T_{return}(n)$

Como , la expresión se simplifica a:

$T(n) = T_{bucle}(n) + c_1$

Para calcular , analizamos las iteraciones de cada bucle. A diferencia de los bucles anidados independientes, en este caso los límites superiores de los bucles interno e intermedio dependen de la variable del bucle externo.

Bucle externo (i): Va de a con incrementos de 1.
Bucle intermedio (j): Va de a con incrementos de 1. Su número de iteraciones es .
Bucle interno (k): Va de a con incrementos de 1. Su número de iteraciones es .

Dado que los bucles j y k son independientes entre sí pero ambos dependen de i, el número total de iteraciones de los dos bucles más internos para un valor dado de es .

Podemos expresar el tiempo de ejecución del bucle total mediante un triple sumatorio:

$T_{bucle}(n) = \sum_{i=1}^{n} \sum_{j=1}^{i} \sum_{k=1}^{i} c_2$

Donde es el coste constante de las operaciones ejecutadas en el bucle interno (línea 4).

Resolvemos los sumatorios de adentro hacia afuera. Primero el sumatorio interno en :

$\sum_{k=1}^{i} c_2 = c_2 \cdot i$

Luego el sumatorio intermedio en :

$\sum_{j=1}^{i} (c_2 \cdot i) = c_2 \cdot i \sum_{j=1}^{i} 1 = c_2 \cdot i \cdot i = c_2 \cdot i^2$

Ahora sustituimos este resultado en el sumatorio externo en :

$T_{bucle}(n) = \sum_{i=1}^{n} (c_2 \cdot i^2) = c_2 \sum_{i=1}^{n} i^2$

Recordamos que la suma de los cuadrados de los primeros números naturales es .

Aplicando esta fórmula:

$T_{bucle}(n) = c_2 \cdot \frac{n(n+1)(2n+1)}{6} = c_2 \cdot \frac{2n^3 + 3n^2 + n}{6}$

Desarrollando la fracción:

$T_{bucle}(n) = \frac{c_2}{3} n^3 + \frac{c_2}{2} n^2 + \frac{c_2}{6} n$

Sustituyendo en la expresión original de :

$T(n) = \frac{c_2}{3} n^3 + \frac{c_2}{2} n^2 + \frac{c_2}{6} n + c_1$

14.2 Cálculo del orden de complejidad

Para determinar el orden de complejidad, realizamos el análisis asintótico:

Descartamos los términos de menor orden. Los términos proporcionales a , y las constantes () son despreciables frente al término polinómico de mayor grado cuando es grande.
Descartamos las constantes multiplicativas. El factor no afecta al crecimiento asintótico de la función.

El término dominante es , por lo que el algoritmo tiene una complejidad cúbica (polinómica de grado 3).

$T(n) \in \mathcal{O}(n^3)$

Ejercicio 15

function ejercicio15(int n)
    for (int i = 1; i <= n; i++)                    // Línea 1
        for(int j = 1; j <= i; j++)                 // Línea 2
            for(int k = 1; k <= j; k++)             // Línea 3
                print(i + j + k)                    // Línea 4
            end_for                                 // Línea 5
        end_for                                     // Línea 6
    end_for                                         // Línea 7
    return n                                        // Línea 8
end_function

15.1 Cálculo del

El tiempo de ejecución de la función viene dado por la suma del tiempo de ejecución del bucle anidado y el retorno:

$T(n) = T_{bucle}(n) + T_{return}(n)$

Como , la expresión se simplifica a:

$T(n) = T_{bucle}(n) + c_1$

Bucle externo (i): Va de a con incrementos de 1.
Bucle intermedio (j): Va de a con incrementos de 1.
Bucle interno (k): Va de a con incrementos de 1. Su número de iteraciones depende del valor de .

Dado que los bucles están anidados y cada uno depende del anterior, el número total de iteraciones se calcula mediante un triple sumatorio:

$T_{bucle}(n) = \sum_{i=1}^{n} \sum_{j=1}^{i} \sum_{k=1}^{j} c_2$

Donde es el coste constante de las operaciones ejecutadas en el bucle interno (línea 4).

Resolvemos los sumatorios de adentro hacia afuera. Primero el sumatorio interno en :

$\sum_{k=1}^{j} c_2 = c_2 \cdot j$

Luego el sumatorio intermedio en :

$\sum_{j=1}^{i} (c_2 \cdot j) = c_2 \sum_{j=1}^{i} j = c_2 \cdot \frac{i(i+1)}{2} = \frac{c_2}{2} (i^2 + i)$

Ahora sustituimos este resultado en el sumatorio externo en :

$T_{bucle}(n) = \sum_{i=1}^{n} \frac{c_2}{2} (i^2 + i) = \frac{c_2}{2} \left( \sum_{i=1}^{n} i^2 + \sum_{i=1}^{n} i \right)$

Recordamos las fórmulas de las sumas:

Aplicando las fórmulas:

$T_{bucle}(n) = \frac{c_2}{2} \left( \frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2} \right)$

Para simplificar esta expresión, realizamos los siguientes pasos algebraicos.

Factorizamos el término común :

$T_{bucle}(n) = \frac{c_2 \cdot n(n+1)}{2} \left( \frac{2n+1}{6} + \frac{1}{2} \right)$

Sumamos las fracciones dentro del paréntesis (denominador común 6):

$\frac{2n+1}{6} + \frac{3}{6} = \frac{2n+4}{6} = \frac{2(n+2)}{6} = \frac{n+2}{3}$

Multiplicamos los resultados para obtener la fórmula compacta:

$T_{bucle}(n) = \frac{c_2 \cdot n(n+1)}{2} \cdot \frac{n+2}{3} = c_2 \cdot \frac{n(n+1)(n+2)}{6}$

Desarrollamos el polinomio y distribuimos el denominador:

$T_{bucle}(n) = c_2 \cdot \frac{n^3 + 3n^2 + 2n}{6} = \frac{c_2}{6} n^3 + \frac{c_2}{2} n^2 + \frac{c_2}{3} n$

Sustituyendo en la expresión original de :

$T(n) = \frac{c_2}{6} n^3 + \frac{c_2}{2} n^2 + \frac{c_2}{3} n + c_1$

15.2 Cálculo del orden de complejidad

Para determinar el orden de complejidad, realizamos el análisis asintótico:

Descartamos los términos de menor orden. Los términos proporcionales a , y las constantes () son despreciables frente al término polinómico de mayor grado cuando es grande.
Descartamos las constantes multiplicativas. El factor no afecta al crecimiento asintótico de la función.

El término dominante es , por lo que el algoritmo tiene una complejidad cúbica (polinómica de grado 3).

$T(n) \in \mathcal{O}(n^3)$

4. Bucles con while

Ejercicio 16

function ejercicio16(int n)
    while (n > 1)                       // Línea 1
        print(n)                        // Línea 2
        n = n / 2                       // Línea 3
    end_while                           // Línea 4
    return 0                            // Línea 5
end_function

16.1 Cálculo del

El tiempo de ejecución de la función viene dado por la suma del tiempo de ejecución del bucle y el tiempo de ejecución de la operación de retorno:

$T(n) = T_{bucle}(n) + T_{return}(n)$

Como , donde es el tiempo constante de la operación de retorno:

$T(n) = T_{bucle}(n) + c_1$

Para determinar el número de iteraciones del bucle while (líneas 1-4), analizamos la progresión geométrica decreciente de los valores que toma la variable :

Iteración 0:
Iteración 1:
Iteración 2:
…
Iteración k:

El bucle continúa iterando mientras se cumpla la condición . Para despejar el número de iteraciones en la última vuelta (), establecemos la inecuación para el límite de iteraciones:

$\begin{aligned} &\frac{n}{2^k} > 1 \\ &n > 2^k \\ &\log_2(n) > \log_2(2^k) \\ &\log_2 n > k \end{aligned}$

Por las propiedades de los logaritmos .

El número total de iteraciones está acotado por .

Podemos expresar el tiempo de ejecución del bucle como un sumatorio donde el índice representa cada iteración:

$T_{bucle}(n) = \sum_{k=1}^{\lfloor \log_2 n \rfloor} c_2$

Donde es el tiempo constante de las operaciones dentro del bucle (líneas 2 y 3). Resolviendo el sumatorio obtenemos:

$T_{bucle}(n) = c_2 \cdot \lfloor \log_2 n \rfloor$

Sustituyendo en la expresión original:

$T(n) = T_{bucle}(n) + c_1 = c_2 \cdot \lfloor \log_2 n \rfloor + c_1$

16.2 Cálculo del orden de complejidad

Para determinar el orden de complejidad, realizamos el análisis asintótico:

Descartamos los términos de menor orden. La constante es un término de orden inferior comparado con .
Descartamos las constantes multiplicativas. La constante no afecta al crecimiento asintótico.
Cambio de base del logaritmo. Todas las funciones logarítmicas pertenecen al mismo orden de complejidad, independientemente de la base.

El término dominante es , por lo que el algoritmo tiene una complejidad logarítmica.

$T(n) \in \mathcal{O}(\log n)$

5. Algoritmos recursivos

Ejercicio 17

long int factorial(long int n) {
    if (n <= 1)                         // Línea 1
        return 1;                       // Línea 2
    else                                // Línea 3
        return n * factorial(n - 1);    // Línea 4
}

17.1 Cálculo de la ecuación de recurrencia

El tiempo de ejecución de un algoritmo recursivo se expresa mediante una ecuación de recurrencia, donde se separa el tiempo de ejecución del caso base del tiempo del caso recursivo.

Para la función factorial(n), consideramos:

: Tiempo de ejecución del caso base ().
: Tiempo constante de las operaciones realizadas en cada llamada recursiva (comparaciones, resta, multiplicación y retorno).

La ecuación de recurrencia queda expresada como:

$T(n) = \begin{cases} c_1 & \text{si } n \leq 1 \\ T(n-1) + c_2 & \text{si } n > 1 \end{cases}$

17.2 Resolución de la ecuación

Para encontrar una expresión no recursiva de , utilizamos el método de sustitución:

Partimos de la expresión original para el caso recursivo:

$T(n) = T(n-1) + c_2 \quad \text{(1)}$
Obtenemos la expresión de sustituyendo por en la ecuación original:

$T(n-1) = T(n-1-1) + c_2 = T(n-2) + c_2 \quad \text{(2)}$
Sustituimos la ecuación (2) en la (1):

$T(n) = (T(n-2) + c_2) + c_2 = T(n-2) + 2c_2 \quad \text{(3)}$
Repetimos el proceso para :

$T(n-2) = T(n-3) + c_2 \quad \text{(4)}$

$T(n) = (T(n-3) + c_2) + 2c_2 = T(n-3) + 3c_2 \quad \text{(5)}$
Podemos inferir que tras sustituciones, el tiempo de ejecución está dado por:

$T(n) = T(n-i) + i \cdot c_2 \quad \text{(6)}$
El proceso de sustitución termina cuando alcanzamos el caso base (). Despejando :
Sustituimos el valor de en la ecuación (6):

$T(n) = T(1) + (n-1)c_2 \quad \text{(7)}$
Como sabemos que (caso base), la expresión final es:

$T(n) = c_1 + (n-1)c_2 = c_2 n + (c_1 - c_2) \quad \text{(8)}$

17.3 Cálculo del orden de complejidad

Para determinar el orden de complejidad, realizamos el análisis asintótico sobre la expresión obtenida:

Descartamos los términos de menor orden. En la expresión , el término dominante es el que depende de . La constante es despreciable cuando es grande.
Descartamos las constantes multiplicativas. El factor no afecta a la tasa de crecimiento de la función.

El término dominante es , por lo que el algoritmo tiene una complejidad lineal.

$T(n) \in \mathcal{O}(n)$

Ejercicio 18

int recursiva1(int n) {
    if (n <= 1)                         // Línea 1
        return 1;                       // Línea 2
    else                                // Línea 3
        return 2 * recursiva1(n / 2);   // Línea 4
}

18.1 Cálculo de la ecuación de recurrencia

Para la función recursiva1(n), definimos:

: Tiempo de ejecución del caso base ().
: Tiempo constante de las operaciones realizadas en cada llamada recursiva (comparación, división por 2, multiplicación por 2 y retorno).

La ecuación de recurrencia queda expresada como:

$T(n) = \begin{cases} c_1 & \text{si } n \leq 1 \\ T(n/2) + c_2 & \text{si } n > 1 \end{cases}$

18.2 Resolución de la ecuación

Para encontrar una expresión no recursiva de , utilizamos el método de sustitución:

Partimos de la expresión original para el caso recursivo:

$T(n) = T(n/2) + c_2 \quad \text{(1)}$
Obtenemos la expresión de sustituyendo por en la ecuación original:

$T(n/2) = T((n/2)/2) + c_2 = T(n/2^2) + c_2 \quad \text{(2)}$
Sustituimos la ecuación (2) en la (1):

$T(n) = (T(n/2^2) + c_2) + c_2 = T(n/2^2) + 2c_2 \quad \text{(3)}$
Repetimos el proceso para el siguiente paso:

$T(n/2^2) = T(n/2^3) + c_2 \quad \text{(4)}$

$T(n) = (T(n/2^3) + c_2) + 2c_2 = T(n/2^3) + 3c_2 \quad \text{(5)}$
Podemos inferir que tras sustituciones, el tiempo de ejecución está dado por:

$T(n) = T(n/2^i) + i \cdot c_2 \quad \text{(6)}$
El proceso de sustitución termina cuando alcanzamos el caso base (). Despejamos :

$2^i = n \implies i = \log_2 n$
Sustituimos el valor de en la ecuación (6):

$T(n) = T(1) + (\log_2 n) \cdot c_2 \quad \text{(7)}$
Como sabemos que (caso base), la expresión final es:

$T(n) = c_1 + c_2 \log_2 n \quad \text{(8)}$

18.3 Cálculo del orden de complejidad

Para determinar el orden de complejidad, realizamos el análisis asintótico sobre la expresión obtenida:

Descartamos los términos de menor orden. La constante es un término de orden inferior comparado con .
Descartamos las constantes multiplicativas. El factor no afecta a la tasa de crecimiento asintótico.
Cambio de base del logaritmo. Todas las funciones logarítmicas pertenecen al mismo orden de complejidad, independientemente de la base del logaritmo.

El término dominante es , por lo que el algoritmo tiene una complejidad logarítmica.

$T(n) \in \mathcal{O}(\log n)$

Ejercicio 19

int recursiva2(int n, int x) {
    int i;
    if (n <= 1)                         // Línea 1
        return 1;                       // Línea 2
    else {                              // Línea 3
        for (i = 1; i <= n; i++)        // Línea 4
            x = x + 1;                  // Línea 5
        return recursiva2(n - 1, x);    // Línea 6
    }
}

19.1 Cálculo de la ecuación de recurrencia

Para la función recursiva2(n, x), definimos:

: Tiempo de ejecución del caso base ().
: Tiempo constante asociado a cada iteración del bucle for (líneas 4 y 5).
Consideramos que el resto de operaciones constantes se asimilan en el coste del bucle o en las constantes finales.

La ecuación de recurrencia es:

$T(n) = \begin{cases} c_1 & \text{si } n \leq 1 \\ T(n-1) + c_2 n & \text{si } n > 1 \end{cases}$

19.2 Resolución de la ecuación

Para encontrar una expresión no recursiva de , utilizamos el método de sustitución:

Partimos de la expresión original para el caso recursivo:

$T(n) = T(n-1) + c_2 n \quad \text{(1)}$
Obtenemos la expresión de sustituyendo en la ecuación original:

$T(n-1) = T(n-2) + c_2(n-1) \quad \text{(2)}$
Sustituimos la ecuación (2) en la (1):

$T(n) = (T(n-2) + c_2(n-1)) + c_2 n = T(n-2) + c_2(n + n-1) \quad \text{(3)}$
Repetimos el proceso para :

$T(n-2) = T(n-3) + c_2(n-2) \quad \text{(4)}$

$T(n) = (T(n-3) + c_2(n-2)) + c_2(n + n-1) = T(n-3) + c_2(n + n-1 + n-2) \quad \text{(5)}$
Podemos inferir que tras sustituciones, el tiempo de ejecución está dado por:

$T(n) = T(n-i) + c_2 \sum_{k=0}^{i-1} (n-k) \quad \text{(6)}$
El proceso termina cuando alcanzamos el caso base (), lo que implica . Sustituimos en la ecuación (6):

$T(n) = T(1) + c_2 \sum_{k=0}^{n-2} (n-k) \quad \text{(7)}$
Evaluamos el sumatorio. Representa la suma de los enteros desde hasta :

$\sum_{k=0}^{n-2} (n-k) = n + (n-1) + (n-2) + \dots + 2 = \left( \sum_{j=1}^{n} j \right) - 1$
Aplicando la fórmula de la suma de los primeros enteros ():

$T(n) = c_1 + c_2 \left( \frac{n(n+1)}{2} - 1 \right) = \frac{c_2}{2} n^2 + \frac{c_2}{2} n + (c_1 - c_2) \quad \text{(8)}$

19.3 Cálculo del orden de complejidad

Para determinar el orden de complejidad, realizamos el análisis asintótico sobre la expresión obtenida:

Descartamos los términos de menor orden. Los términos proporcionales a y las constantes son despreciables frente a cuando es grande.
Descartamos las constantes multiplicativas. El factor no afecta al crecimiento asintótico.

El término dominante es , por lo que el algoritmo tiene una complejidad cuadrática.

$T(n) \in \mathcal{O}(n^2)$

Ejercicio 20

int recursiva3(int n) {
    if (n <= 1)                                       // Línea 1
        return 1;                                     // Línea 2
    else                                              // Línea 3
        return recursiva3(n - 1) + recursiva3(n - 1); // Línea 4
}

20.1 Cálculo de la ecuación de recurrencia

Para la función recursiva3(n), definimos:

: Tiempo de ejecución del caso base ().
: Tiempo constante asociado a las operaciones en el caso recursivo (comparación, resta, suma de los resultados y retorno).

La ecuación de recurrencia es:

$T(n) = \begin{cases} c_1 & \text{si } n \leq 1 \\ 2T(n-1) + c_2 & \text{si } n > 1 \end{cases}$

20.2 Resolución de la ecuación

Para encontrar una expresión no recursiva de , utilizamos el método de sustitución:

Partimos de la expresión original para el caso recursivo:

$T(n) = 2T(n-1) + c_2 \quad \text{(1)}$
Obtenemos la expresión de sustituyendo en la ecuación original:

$T(n-1) = 2T(n-2) + c_2 \quad \text{(2)}$
Sustituimos la ecuación (2) en la (1):

$T(n) = 2(2T(n-2) + c_2) + c_2 = 2^2 T(n-2) + 2c_2 + c_2 = 4T(n-2) + 3c_2 \quad \text{(3)}$
Repetimos el proceso para :

$T(n-2) = 2T(n-3) + c_2 \quad \text{(4)}$

$T(n) = 4(2T(n-3) + c_2) + 3c_2 = 2^3 T(n-3) + 4c_2 + 3c_2 = 8T(n-3) + 7c_2 \quad \text{(5)}$
Podemos inferir que tras sustituciones, el tiempo de ejecución está dado por:

$T(n) = 2^i T(n-i) + (2^i - 1)c_2 \quad \text{(6)}$
El proceso termina cuando alcanzamos el caso base (), lo que implica . Sustituimos en la ecuación (6):

$T(n) = 2^{n-1} T(1) + (2^{n-1} - 1)c_2 \quad \text{(7)}$
Como sabemos que , simplificamos la expresión:

$T(n) = 2^{n-1} c_1 + 2^{n-1} c_2 - c_2 = 2^{n-1}(c_1 + c_2) - c_2$

$T(n) = \frac{c_1 + c_2}{2} \cdot 2^n - c_2 \quad \text{(8)}$

20.3 Cálculo del orden de complejidad

Para determinar el orden de complejidad, realizamos el análisis asintótico sobre la expresión obtenida:

Descartamos los términos de menor orden. La constante es despreciable frente al crecimiento exponencial de cuando es grande.
Descartamos las constantes multiplicativas. El factor no afecta a la tasa de crecimiento asintótico.

El término dominante es , por lo que el algoritmo tiene una complejidad exponencial.

$T(n) \in \mathcal{O}(2^n)$

6. Referencias

Algorithm analysis: Exercises with solutions for AAHPS tutorials. Matej Pičulin.
Analysis of Algorithms: Practice Examples. Princeton University. Ibrahim Albluw.
Introducción al Análisis y al Diseño de Algoritmos. María del Carmen Gómez Fuentes, Jorge Cervantes Ojeda.

7. Licencia

Licencia CC BY-NC-ND 4.0

Esta licencia exige que quienes reutilicen el material otorguen el debido crédito al autor. Permite copiar y redistribuir el material en cualquier medio o formato, únicamente en su forma original, y solo para fines no comerciales.