No post anterior, discutimos a análise de loops . Muitos algoritmos são recursivos por natureza. Quando os analisamos, obtemos uma relação de recorrência para a complexidade do tempo. Obtemos o tempo de execução em uma entrada de tamanho n como uma função de n e o tempo de execução em entradas de tamanhos menores. Por exemplo, em Merge Sort , para classificar um determinado array, nós o dividimos em duas metades e repetimos recursivamente o processo para as duas metades. Finalmente mesclamos os resultados. A complexidade de tempo de Merge Sort pode ser escrita como T (n) = 2T (n / 2) + cn. Existem muitos outros algoritmos como Pesquisa Binária, Torre de Hanói, etc. 

Existem basicamente três maneiras de resolver as recorrências. 

1) Método de substituição : fazemos uma estimativa para a solução e, em seguida, usamos a indução matemática para provar que a estimativa está correta ou incorreta. 

For example consider the recurrence T(n) = 2T(n/2) + n

We guess the solution as T(n) = O(nLogn). Now we use induction
to prove our guess.

We need to prove that T(n) <= cnLogn. We can assume that it is true
for values smaller than n.

T(n) = 2T(n/2) + n
    <= 2cn/2Log(n/2) + n
    =  cnLogn - cnLog2 + n
    =  cnLogn - cn + n
    <= cnLogn

2) Método da árvore de recorrência: Neste método, desenhamos uma árvore de recorrência e calculamos o tempo gasto por cada nível da árvore. Por fim, somamos o trabalho realizado em todos os níveis. Para desenhar a árvore de recorrência, partimos da recorrência dada e continuamos desenhando até encontrar um padrão entre os níveis. O padrão é normalmente uma série aritmética ou geométrica. 
 

For example consider the recurrence relation 
T(n) = T(n/4) + T(n/2) + cn2

           cn2
         /      \
     T(n/4)     T(n/2)

If we further break down the expression T(n/4) and T(n/2), 
we get following recursion tree.

                cn2
           /           \      
       c(n2)/16      c(n2)/4
      /      \          /     \
  T(n/16)     T(n/8)  T(n/8)    T(n/4) 
Breaking down further gives us following
                 cn2
            /            \      
       c(n2)/16          c(n2)/4
       /      \            /      \
c(n2)/256   c(n2)/64  c(n2)/64    c(n2)/16
 /    \      /    \    /    \       /    \  

To know the value of T(n), we need to calculate sum of tree 
nodes level by level. If we sum the above tree level by level, 
we get the following series
T(n)  = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + ....
The above series is geometrical progression with ratio 5/16.

To get an upper bound, we can sum the infinite series. 
We get the sum as (n2)/(1 - 5/16) which is O(n2)

3) Método Mestre: 
O Método Mestre é uma forma direta de obter a solução. O método mestre funciona apenas para os seguintes tipos de recorrências ou para recorrências que podem ser transformadas no seguinte tipo. 
 

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

Existem três casos a seguir: 
1. Se f (n) = O (n ^c ) onde c <Log _b a, então T (n) = Θ (n ^{Log _b a} ) 

2. Se f (n) = Θ (n ^c ) onde c = Log _b a então T (n) = Θ (n ^c Log n) 

3. Se f (n) = Ω (n ^c ) onde c> Log _b a então T (n) = Θ (f (n))

Como é que isso funciona?  
O método mestre é derivado principalmente do método da árvore de recorrência. Se desenharmos a árvore de recorrência de T (n) = aT (n / b) + f (n), podemos ver que o trabalho realizado na raiz é f (n) e o trabalho realizado em todas as folhas é Θ (n ^c ), onde c é Log _b a. E a altura da árvore de recorrência é Log _b n 
 

No método da árvore de recorrência, calculamos o trabalho total realizado. Se o trabalho realizado nas folhas for mais polinomialmente, então as folhas são a parte dominante e nosso resultado passa a ser o trabalho realizado nas folhas (Caso 1). Se o trabalho realizado nas folhas e na raiz for assintoticamente igual, nosso resultado será a altura multiplicada pelo trabalho realizado em qualquer nível (Caso 2). Se o trabalho realizado na raiz for assintoticamente maior, nosso resultado será o trabalho realizado na raiz (Caso 3). 

Exemplos de alguns algoritmos padrão cuja complexidade de tempo pode ser avaliada usando Master Method 
Merge Sort : T (n) = 2T (n / 2) + Θ (n). Ele cai no caso 2 porque c é 1 e Log _b a] também é 1. Portanto, a solução é Θ (n Logn) 

Pesquisa binária : T (n) = T (n / 2) + Θ (1). Também cai no caso 2, pois c é 0 e Log _b a também é 0. Portanto, a solução é Θ (Logn) 

Notas: 
1) Não é necessário que uma recorrência da forma T (n) = aT (n / b) + f (n) possa ser resolvida usando o Teorema Mestre. Os três casos fornecidos têm algumas lacunas entre eles. Por exemplo, a recorrência T (n) = 2T (n / 2) + n / Logn não pode ser resolvida usando o método mestre. 

2) Caso 2 pode ser estendido para f (n) = Θ (n ^c Log ^k n) 
Se f (n) = Θ (n ^c Log ^k n) para alguma constante k> = 0 e c = Log _b a, então T (n) = Θ (n ^c Log ^{k + 1} n) 

Prática de problemas e soluções no teorema mestre. 

Next - Análise de Algoritmo | Conjunto 5 (Introdução à Análise Amortizada) 

Referências:  
http://en.wikipedia.org/wiki/Master_theorem  
MIT Video Lecture on Asymptotic Notation | Recorrências | Substituição, Método Mestre  
Introdução aos Algoritmos 3ª Edição por Clifford Stein, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest 

Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima