Sea T(n) una función definida por la recurrencia
T(n) = 2T(n/2) + √n para n ≥ 2 y
T(1) = 1
¿Cuál de las siguientes afirmaciones es verdadera?
(A) T(n) = θ(log n)
(B) T(n) = θ(√n)
(C) T(n) = θ(n)
(D) T(n) = θ(n log n)
Respuesta: (C)
Explicación: n (log b a) = n que es = n^(1-.5) = O(sqrt n)
luego aplicando el caso 1 del método maestro obtenemos T(n) = Θ (norte)
Consulte https://www.geeksforgeeks.org/analysis-algorithm-set-4-master-method-solution-recurrences/ para obtener más detalles.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA