Algoritmos y Estructuras de Datos (VJ1215)

Relación de recurrencia: T(n) = 2 T(n/2) + O(1) siendo n la talla del vector.

Podemos resolverla aplicando el Teorema Maestro con a = 2, b = 2, k = 0 y p = 0. Tenemos el caso a > b^k, y su solución es T(n) = O(n^log₂2) = O(n).