b'\n_START_ARTICLE_\nTeorema maestro\n_START_PARAGRAPH_\nEn el an\xc3\xa1lisis de algoritmos, el teorema maestro proporciona una soluci\xc3\xb3n sencilla en t\xc3\xa9rminos asint\xc3\xb3ticos  (usando una Cota superior asint\xc3\xb3tica) para ecuaciones de recurrencia que ocurren en muchos algoritmos recursivos tales como en el Algoritmo divide y vencer\xc3\xa1s. Fue popularizado por el libro Introducci\xc3\xb3n a los algoritmos por Cormen, Leiserson, Rivest, y Stein, en el cual fue tanto introducido como probado formalmente. No todas las ecuaciones de recurrencia pueden ser resueltas con el uso del teorema maestro.\n_START_SECTION_\nIntroducci\xc3\xb3n\n_START_PARAGRAPH_\nConsidere un problema que puede ser resuelto a trav\xc3\xa9s de un algoritmo recursivo como el siguiente:_NEWLINE_ procedimiento T( n\xc2\xa0: tama\xc3\xb1o del problema ) definici\xc3\xb3n:_NEWLINE_   if n < 1 then exit_NEWLINE__NEWLINE_   Hacer trabajo f(n)_NEWLINE__NEWLINE_   T(n/b)_NEWLINE_   T(n/b)_NEWLINE_   ...repetir una cantidad de  a veces..._NEWLINE_   T(n/b)_NEWLINE_ fin procedimiento_NEWLINE_En el algoritmo mostrado arriba se divide el problema original en una cantidad menor de subproblemas de manera recursiva, cada uno de estos subproblemas siendo del tama\xc3\xb1o de n/b. Esto podr\xc3\xada ser visualizado como la construcci\xc3\xb3n de un \xc3\xa1rbol de llamadas al problema, siendo cada nodo del \xc3\xa1rbol una instancia recursiva del mismo y sus hijos siendo instancias de las llamadas subsiguientes. En el ejemplo de arriba, cada nodo tendr\xc3\xada un n\xc3\xbamero a de hijos. Cada nodo har\xc3\xa1 la cantidad de trabajo correspondiente al tama\xc3\xb1o del subproblema n, pasado a esa instancia en particular, estando la cantidad de trabajo realizado determinado por . El trabajo total realizado por todas las llamadas del \xc3\xa1rbol es la suma de los trabajos hechos por cada uno de los nodos del \xc3\xa1rbol._NEWLINE_Algoritmos como el descrito arriba pueden ser representados por una relaci\xc3\xb3n de recurrencia como la siguiente:_NEWLINE_. Esta relaci\xc3\xb3n de recurrencia puede ser sucesivamente sustituida en s\xc3\xad misma y expandida hasta obtener una expresi\xc3\xb3n que represente la cantidad total de trabajo.\xe2\x80\x8b_NEWLINE_El teorema maestro nos permite f\xc3\xa1cilmente calcular el tiempo de ejecuci\xc3\xb3n de este tipo de algoritmos recursivos en notaci\xc3\xb3n de Cota superior asint\xc3\xb3tica, sin la necesidad de hacer la expansi\xc3\xb3n de las distintas llamadas recursivas.'