PUERTA | Puerta TI 2008 | Pregunta 42

Cuando n = 2 ^2k para algún k ≥ 0, la relación de recurrencia

T(n) = √(2) T(n/2) + √n, T(1) = 1

se evalúa como:
(A) √(n) (log n + 1)
(B) √(n) (log n )
(C) √(n) log √(n)
(D) n log √(n)

Respuesta: (A)
Explicación: tenga en cuenta que la pregunta se refiere a la solución exacta. El teorema de Master proporciona resultados en forma de notaciones asintóticas . Entonces no podemos aplicar el teorema de Master aquí. Podemos resolver esta recurrencia usando el método de árbol de recurrencia o expansión simple.

T(n) = √(2) T(n/2) + √n
     = √(2) [√(2) T(n/4) + √(n/2) ] + √n
     = 2 T(n/4) + √2 √(n/2) +√n
     = 2[ √2 T(n/8) + √(n/4) ]+√2 √(n/2)+√n
     = √(2^3) T(n/8)+ 2 √(n/4) + √2 √(n/2) +√n
     = √(2^3) T(n/8)+√n +√n +√n
     = √(2^3) T(n/(2^3))+3√n
     .............................................
     = √(2^k) T(n/(2^k))+k√n
     = √(2^logn) + logn √n
     = √n + logn √n
     = √n(logn +1)

Solución alternativa:
esta pregunta se puede hacer fácilmente con el método de sustitución:
T(1)= 1; DADO.
Ahora use n=2 en la relación de recurrencia dada que da 2*(1.414) (dado que el valor de la raíz sobre 2 es 1.414)
ahora al mirar las opciones use n=2 que satisface la opción A.

Cuestionario de esta pregunta