Pregunta 2.d · Prácticas de programación UOC 2023

d. [15%] Evalúa el coste temporal en el peor caso del procedimiento original recursivo, justificando con rigor analítico la formulación matemática de la recurrencia y su deducción.

Solución: En cada nivel de la recursión se verifica una condición booleana simple y se realizan operaciones aritméticas básicas de tiempo constante ($O(1)$), acompañadas de una llamada interna con el tamaño del problema reducido a la mitad ($x/2$). La recurrencia asociada a la función temporal $T(x)$ queda delimitada formalmente como: $$T(x) = \begin{cases} k_1 & \text{si } x < 2 \\ k_2 + T\left(\left\lfloor\frac{x}{2}\right\rfloor\right) & \text{si } x \ge 2 \end{cases}$$ Desplegando la recurrencia mediante sustitución progresiva durante $i$ etapas: $$T(x) = k_2 + T\left(\frac{x}{2}\right)$$ $$= k_2 + \left(k_2 + T\left(\frac{x}{4}\right)\right) = 2k_2 + T\left(\frac{x}{2^2}\right)$$ $$= 3k_2 + T\left(\frac{x}{2^3}\right)$$ $$= \dots$$ $$= i \cdot k_2 + T\left(\frac{x}{2^i}\right)$$ El caso base se alcanza cuando el argumento se reduce a la unidad o inferior, es decir: $$\frac{x}{2^i} = 1 \implies 2^i = x \implies i = \log_2(x)$$ Reemplazando el valor de $i$ en la ecuación general obtenida: $$T(x) = k_2 \log_2(x) + T(1) = k_2 \log_2(x) + k_1$$ Se concluye, por consiguiente, que el algoritmo presenta una complejidad asintótica de orden logarítmico: $O(\log x)$.

Orden de complejidad asintótica final:

Solución: $O(\log x)$ / $O(\log_2 x)$