Deseamos compartirte la mejor solución que hemos encontrado on line. Queremos que te sirva de ayuda y si deseas comentarnos algo que nos pueda ayudar a perfeccionar nuestra información hazlo con libertad.
Solución:
Para dar una respuesta directa a su pregunta, se trata de adivinar en el paso $(a)$.
$T(n) = n log_2 (n) + n$ es la conjetura que hiciste en el paso $(a)$. Usando eso, reemplaza $n = fracn2$, $T(fracn2) = fracn2 log_2 (fracn2) + fracn2$.
$T(fracn2) = fracn2 (log_2 (n) – log_2(2)) + fracn2 = fracn 2 log_2 (n) – fracn2 + fracn2 = fracn2 log_2 (n)$
Por lo tanto, $T(n) = 2 T(fracn2) + n = 2 fracn2 log_2 (n) + n = n log_2 (n) + n$
Mientras resuelve algunas recurrencias, es bueno reconocer algunas cosas buenas sobre la recurrencia que realmente está resolviendo. Por ejemplo, en esta recurrencia, observe que en cada paso está dividiendo $n$ por $2$. Entonces estrictamente hablando a través de la recurrencia solo puedes obtener $T(2^m)$ donde $m in mathbbN$. Por ejemplo, $T(3)$ no se puede obtener usando esta recurrencia. Sin embargo, tales recurrencias surgen cuando haces ciertas cosas, cuando $n$ es realmente grande, usando recursivamente, por ejemplo, un árbol binario. Cuando $n$ es realmente grande, le interesa principalmente cómo se comporta la solución en un sentido asintótico y no la expresión precisa de la solución. En tales casos, usted asume que $n=2^m$ por la simplicidad de los cálculos y el costo de todos los $n$ (incluso cuando $n$ no es una potencia de $2$) puede demostrarse que obedece a la solución obtenida por el supuesto de $n=2^m$, en un sentido asintótico.
Si tuviera que reescribir la recurrencia en términos de $m$ y llamar a $T(2^m) = S(m)$, entonces obtendríamos
$S(m) = 2 S(m-1) + 2^m$ ya que $fracn2 = 2^m-1$.
$S(m-1) = 2 S(m-2) + 2^m-1$.
$S(m) = 4 S(m-2) + 2^m + 2^m$ y así sucesivamente (inducción oculta aquí) para obtener
$S(m) = 2^m S(0) + 2^m + 2^m + cdots + 2^m + 2^m = m 2^m + 2^m$.
Por lo tanto, $T(n) = n log_2(n) + n$ ya que $n = 2^m$, es decir, $m = log_2(n)$
Como dicen, es una conjetura. Si (como en a) $T(n)=n lg n + n$ simplemente sustituye para obtener el que pide “Hasta aquí”. Entonces, la verdadera pregunta es si la inducción está justificada. El punto es que si la expresión para T es válida hasta n, es válida hasta 2n (y debe explicar en este caso qué sucede con $n$ impares), entonces es válida para todos los $n$.