Pregunta 2.d y 2.e · Prácticas de programación UOC 2021

d) Orden de complejidad asintótica obtenido

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

d) [15%] Efectúa el estudio formal del coste computacional (complejidad temporal) correspondiente al diseño recursivo original a través de su relación de recurrencia detallada paso a paso.

Solución: Relación de recurrencia: $$\begin{cases} T(0) = k_0 \\ T(x) = T(x-1) + k_1, & \text{si } x > 0 \end{cases}$$ Desarrollo por sustitución regresiva: $$T(x) = T(x-1) + k_1 = T(x-2) + 2k_1 = \dots = T(x-i) + i \cdot k_1$$ Para el caso base $x - i = 0 \implies i = x$: $$T(x) = T(0) + x \cdot k_1 = k_0 + x \cdot k_1 \in O(x)$$

e) Decisión respecto a una alternativa logarítmica

Solución: Inconveniente

e) [5%] En caso de que se concibiera una variante de este método cuyo orden de complejidad temporal resultase de clase logarítmica O(log n), razona en un párrafo breve de 4 a 5 líneas la conveniencia o inconveniencia de sustituir la implementación actual por dicha propuesta.

Solución: Resultaría inconveniente porque el tipo `int` desborda a partir de $x \ge 13$ ($13! > 2^{31}-1$). Al estar acotado a un máximo de 12 iteraciones, el coste es despreciable y una alternativa logarítmica solo añadiría sobrecarga de control y constantes ocultas.