b'\n_START_ARTICLE_\nTeorema mestre (an\xc3\xa1lise de algoritmos)\n_START_PARAGRAPH_\nNa an\xc3\xa1lise de algoritmos, o teorema mestre para recorr\xc3\xaancias de divis\xc3\xa3o e conquista\xc2\xa0fornece uma an\xc3\xa1lise assint\xc3\xb3tica (usando a nota\xc3\xa7\xc3\xa3o Grande-O) para rela\xc3\xa7\xc3\xb5es de recorr\xc3\xaancia\xc2\xa0que ocorrem na an\xc3\xa1lise de muitos algoritmos de divis\xc3\xa3o e conquista. A abordagem foi apresentada\xc2\xa0pela primeira vez por Jon Bentley, Dorothea Haken, e James B. Saxe , em 1980, onde foi descrito como um "m\xc3\xa9todo unificador" para a solu\xc3\xa7\xc3\xa3o de tais recorr\xc3\xaancias. O nome "teorema mestre" foi popularizado pelo livro de algoritmos amplamente utilizado Algoritmos: teoria e pr\xc3\xa1tica\xc2\xa0por Cormen, Leiserson, Rivest\xc2\xa0e\xc2\xa0Stein. _NEWLINE_Nem todas as rela\xc3\xa7\xc3\xb5es de recorr\xc3\xaancia podem ser resolvidas com o uso do teorema; suas generaliza\xc3\xa7\xc3\xb5es incluem o m\xc3\xa9todo de Akra-Bazzi.\n_START_SECTION_\nIntrodu\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nConsidere um problema que pode ser resolvido usando um algoritmo recursivo\xc2\xa0como o algoritmo a seguir:_NEWLINE_ procedimento p(entrada x de tamanho n):_NEWLINE_ se n < alguma constante k:_NEWLINE_   Resolver x diretamente, sem recurs\xc3\xa3o_NEWLINE_ sen\xc3\xa3o:_NEWLINE_   Criar um subproblema de x, cada um com tamanho n/b_NEWLINE_   Chamar o procedimento p recursivamente em cada subproblema_NEWLINE_   Combinar os resultados dos subproblemas_NEWLINE_O algoritmo acima divide o problema em um n\xc3\xbamero de subproblemas recursivamente, cada subproblema sendo de tamanho n/b. A sua \xc3\xa1rvore de chamadas\xc2\xa0tem um n\xc3\xb3 para cada chamada recursiva, com os filhos do n\xc3\xb3 sendo as outras chamadas feitas a partir dessa chamada. As folhas da \xc3\xa1rvore s\xc3\xa3o os casos base da recurs\xc3\xa3o, os subproblemas (de tamanho menor do que k) que n\xc3\xa3o se resolve recursivamente. O exemplo acima teria  n\xc3\xb3s-filhos em cada n\xc3\xb3 que n\xc3\xa3o fosse uma folha. Cada n\xc3\xb3 realiza uma quantidade de trabalho que corresponde ao tamanho do sub problema n passado para essa inst\xc3\xa2ncia da chamada recursiva e dada por . A quantidade total de trabalho realizado pelo algoritmo completo \xc3\xa9 a soma do trabalho realizado por todos os n\xc3\xb3s na \xc3\xa1rvore.O tempo de execu\xc3\xa7\xc3\xa3o de um algoritmo, como o \'p\' acima em uma entrada de tamanho \'n\', geralmente denotado por , pode ser expresso pela rela\xc3\xa7\xc3\xa3o de recorr\xc3\xaancia_NEWLINE_onde  \xc3\xa9 o tempo para criar os subproblemas e combinar seus resultados no procedimento acima. Essa equa\xc3\xa7\xc3\xa3o pode ser substitu\xc3\xadda, sucessivamente, por si mesma e se expandir para obter uma express\xc3\xa3o para a quantidade total de trabalho realizado. O teorema mestre permite que muitas rela\xc3\xa7\xc3\xb5es de recorr\xc3\xaancia desta forma serem convertidas para nota\xc3\xa7\xc3\xa3o teta diretamente, sem fazer uma expans\xc3\xa3o da rela\xc3\xa7\xc3\xa3o recursiva.'