Buenas, estaba haciendo un ejercicio de resolución de una recurrencia y he obtenido esta solución pero no sé si es correcta, expongo el enunciado y mi planteamiento
Enunciado:
Halla una expresión no recursiva para la siguiente recurrencia por el método de expansión por recurrencias:
\( T(n) = T(n/3) + n \)
donde n es una potencia de 3(\( n=3^k \) para k = 1,2,...) y donde \( T(1) = 0 \)
Indica además el orden de T(n).
Mi idea es la siguiente:
\(
T(n)= \left\{ \begin{array}{lcc}
0 & si & n = 1 , k=0 \\
\\ 3 & si & n=3 , k=1 \\
\\ 9 & si & n=9, k=2 \\
\\ T(n/3)+n
\end{array}
\right.
\)
Busco obtener una fórmula general:
\( T(n) = T(n/3)+n = (T(n/3^2+n/3)+n = (T(n/3^3) + n/3^2 + n/3) + n \)
\( T(n/3) = T(n/3^2)+n/3 \)
\( T(n/9) = T(n/3^3) + n/3^2 \)
Mi fórmula general para representar esto sería la siguiente:
\( T(n) = T(\displaystyle\frac{n}{3^k}+ \displaystyle\sum_{i=0}^{k-1}{\displaystyle\frac{n}{3^i}} \)
Igualo al caso recursivo con el general (sólo los términos afectados por las Ts)
\( T(1) = T(\displaystyle\frac{n}{3^k} \)
\( 1 = \displaystyle\frac{n}{3^k} \)
\( \log_{3}(3^k) = \log_{3}(n) \)
\( k = \log_{3}(n) \)
Sustituyo en mi fórmula general la k:
\( T(n) = T(\displaystyle\frac{n}{3^k}+ \displaystyle\sum_{i=0}^{k-1}{\displaystyle\frac{n}{3^i}} \)
\( T(n) = T(1)+ \displaystyle\sum_{i=0}^{ \log_{3}(n)-1}{\displaystyle\frac{n}{3^i}} \)
\( T(n) = 0+ \displaystyle\sum_{i=0}^{ \log_{3}(n)-1}{\displaystyle\frac{n}{3^i}} \)
Y ese sumatorio, al final tiende a un número, así que podríamos decir que el orden de complejidad de T(n) pertenece a O(n)
Es como se me ha ocurrido resolverlo, pero no sé si es correcto, especialmente la fórmula general, ya que no soy muy hábil con los sumatorios.
Gracias y un saludo
