¿Qué tipo de serie/recurrencia es esta?

Question

Estoy tratando de encontrar la solución explícita / suma de los primeros n elementos para la siguiente secuencia:

d(2) = 2
d(n) = d(n/2) + n*log2(n)

¿Pueden ayudarme a averiguar qué tipo de recursión es ésta y cómo puedo encontrar la solución explícita y la suma de los primeros n elementos?

He calculado los primeros elementos, y es así:

2 + 8 + 24 + 64 + ....

(He llegado hasta aquí intentando calcular el tiempo de ejecución asintótico del algoritmo de ordenación bitónica en una arquitectura paralela conectada en anillo, y esta es la última parte pero me he quedado con esta ecuación)

Answer 1

Dado que la recurrencia sólo se define cuando $n$ es una potencia de 2, dejaremos que $n=2^k$ para un número entero $k\ge 1$ . Para facilitar la escritura, denotaremos $\log_2 x\text{ by }\lg x$ por lo que su recurrencia puede escribirse como $$ d(2^k)=\begin{cases} 2 & \text{if }k=1 \\ d(2^{k-1})+k\:2^k & \text{if }k>1 \end{cases} $$ Ahora podemos aplicar repetidamente esta definición a los términos entre paréntesis: $$ \begin{align} d(2^k) &= [d(2^{k-1})]+k\:2^k \\ &= [d(2^{k-2})+(k-1)2^{k-1}] + k\:2^k =[d(2^{k-2})]+(k-1)2^{k-1} + k\:2^k\\ &= [d(2^{k-3})]+(k-2)2^{k-2}+(k-1)2^{k-1} + k\:2^k\\ &= [d(2^{k-4})]+(k-3)2^{k-3}+(k-2)2^{k-2}+(k-1)2^{k-1} + k\:2^k \end{align} $$ y eventualmente terminar con $$ d(2^k)=(1)2^1+(2)2^2+(3)2^3+\cdots+(k-2)2^{k-2}+(k-1)2^{k-1} + k\:2^k $$ Existe una forma cerrada para esto (ver las notas más abajo), pero si no la conoces, podemos obtener una cota superior reescribiendo ligeramente como $$ d(2^k)=(k-(k-1))2^1+(k-(k-1))2^2+\cdots+(k-1)2^{k-1} + k\:2^k $$ y luego separar los términos positivos y negativos: $$ \begin{align} d(2^k)&=[k\:2^1+k\:2^2+\cdots+k\:2^k]-[(k-1)2^1+(k-2)2^2+\cdots + (1)2^{k-1}]\\ &\le k\:2^1+k\:2^2+\cdots+k\:2^k \\ &=2k(1+2+4+\cdots 2^{k-1})\\ &=2k(2^k-1) \end{align} $$ ahora usando el hecho de que $n=2^k$ (y por lo tanto $k=\lg n)$ hemos demostrado que $$ d(n)\le (2\lg n)(n-1) $$ y finalmente tenemos nuestro límite superior asintótico (esperado) $$ d(n)=O(n\lg n) $$

---

Algunas notas adicionales

• En tu último comentario dices que $n\lg n$ funciona "más o menos" como un $n^k$ . Esto es intuitivamente correcto, pero estrictamente hablando sospecho que su versión del Teorema Maestro no se aplica a los términos que no son polinomios.
• He mencionado que hay una forma cerrada para la suma. Se deduce del hecho de que $$ x+2x^2+3x^3+\cdots+kx^k=\frac{x}{(x-1)^2}(kx^{k+1}-(k+1)x^k+1) $$ que se puede obtener de la suma de la serie geométrica $1+x+x^2+\cdots + x^k$ diferenciando. Así tenemos la solución exacta $d(n)=2n(\lg n-1)+2$ que nos da la estimación asintótica más fuerte $d(n)=\Theta(n\lg n)$ .