Pregunta 2.c - Análisis de complejidad · Prácticas de programación UOC Juny 2020

Orden de complejidad asintótica O(...) respecto a x

Solución: $x$ / $n$

c. [30%] Determina la complejidad temporal teórica de la versión recursiva original mediante la formulación y resolución de la relación de recurrencia correspondiente.

Solución: En cada nivel de recursión, el parámetro $x$ disminuye en 1 unidad hasta alcanzar el caso trivial $x = 0$. El caso base consiste en una comparación y una asignación, lo que supone un coste constante $k_1$. El caso recursivo ejecuta una llamada recursiva sobre $x - 1$ junto a operaciones elementales de tiempo acotado (condicional, indexación y asignación), agrupadas en una constante $k_2$. La ecuación de recurrencia que define el tiempo de ejecución $T(x)$ es: $$T(x) = \begin{cases} k_1 & \text{si } x = 0 \\ T(x - 1) + k_2 & \text{si } x > 0 \end{cases}$$ Aplicando sustituciones sucesivas: $$\begin{aligned} T(x) &= T(x - 1) + k_2 \\ &= T(x - 2) + 2k_2 \\ &= T(x - 3) + 3k_2 \\ &= \dots \\ &= T(x - i) + i \cdot k_2 \end{aligned}$$ El proceso finaliza cuando se alcanza la condición de parada $x - i = 0$, es decir, cuando $i = x$: $$T(x) = T(0) + x \cdot k_2 = k_1 + k_2 \cdot x$$ Por tanto, el algoritmo presenta una complejidad asintótica lineal $O(x)$ respecto al parámetro de entrada.