Pregunta 2.c · Prácticas de programación UOC Juny 2020

Deduce formalmente la complejidad computacional del algoritmo en su versión recursiva.

Solución: Tomando como tamaño del problema el parámetro $x$ (número de elementos pendientes por procesar): - Caso base ($x = 0$): solo se evalúa la condición de parada del `if`, por lo que $T(0) = c_0 = O(1)$. - Caso recursivo ($x > 0$): se realizan comparaciones y asignaciones elementales de coste constante más una llamada recursiva con tamaño $x - 1$: $$T(x) = T(x - 1) + c_1$$ Desplegando la recurrencia: $$T(x) = T(x - 1) + c_1 = T(x - 2) + 2c_1 = \dots = T(0) + x \cdot c_1 = c_0 + c_1 x$$ Por lo tanto, la complejidad temporal es de orden lineal: $O(x)$ (o $O(n)$ siendo $n = x$). La complejidad espacial en la pila de llamadas también es $O(x)$ debido a los $x + 1$ marcos de activación anidados.

Complejidad temporal asintótica

Solución: $O(x)$ / $O(n)$

Complejidad espacial asintótica

Solución: $O(x)$ / $O(n)$