Seleccione la complejidad asintótica correcta de un algoritmo con tiempo de ejecución T(n, n) donde
T(x, c) = Θ(x) for c <= 2, T(c, y) = Θ(y) for c <= 2, and T(x, y) = Θ(x+y) + T(x/2, y/2)
(A) Θ(nLogn)
(B) Θ(n 2 )
(C) Θ(n)
(D) Θ(n 2 Logn)
Respuesta: (C)
Explicación: La recurrencia es
T(x, y) = Θ(x+y) + T(x/2, y/2)
Se puede escribir como se muestra a continuación.
T(x, y) = Θ(x+y) + Θ((x+y)/2) + Θ((x+y)/4) + Θ((x+y)/8) ..... T(x, y) = Θ((x+y) + (x+y)/2 + (x+y)/4 + (x+y)/8 ..... )
La expresión anterior forma una serie geométrica con una razón de 2 y un elemento inicial como (x+y)/2
T(x, y) tiene un límite superior por Θ(x+y) ya que la suma de series infinitas es 2(x+y). Tiene el límite inferior de (x+y)
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