Por que existe a condição de regularidade no teorema mestre?

Eu tenho lido Introdução aos algoritmos por Cormen et al. e eu estou lendo a declaração do teorema do mestre começando na página 73 . No caso 3, há também uma condição de regularidade que precisa ser satisfeita para usar o teorema:

... 3. Se

$\qquad \displaystyle f(n) = \Omega(n^{\log_b a + \varepsilon})$

para alguma constante $\varepsilon > 0$ e se

$\qquad \displaystyle af(n/b) \leq cf(n)$      [esta é a condição de regularidade]

para alguma constante e para todas n suficientemente grandes , então ..$c < 1$$n$

Alguém pode me dizer por que a condição de regularidade é necessária? Como o teorema falha se a condição não é satisfeita?

Não é uma prova rigorosa, mas uma explicação "do alto da minha cabeça".

Imagine a recorrência como uma árvore. O terceiro caso cobre o cenário em que o nó raiz domina o tempo de execução assintoticamente, ou seja, a maior parte do trabalho está sendo realizada no nó mísero, na parte superior da árvore de recorrência. Então o tempo de execução é Θ ( f ( n ) ) .$aT(n/b)+f(n)$$\Theta(f(n))$

Para garantir que a raiz realmente funcione mais, você precisa do

.$a f(n/b) \leq cf(n)$

Isso diz que (a quantidade de trabalho realizado na raiz) precisa ser pelo menos tão grande quanto a soma do trabalho realizado nos níveis mais baixos. (A recorrência é chamado um vezes em n / b da entrada).$f(n)$$a$$n/b$

Por exemplo, para a recorrência o trabalho no nível abaixo da raiz é um quarto do tamanho e é feito apenas duas vezes ( n / 4 + n / 4 ) versus n, de modo que a raiz domina .$T(n)=2T(n/4)+n$$(n/4+n/4)$$n$

Mas e se a função não atender à condição de regularidade? Por exemplo, vez de n ? Então, o trabalho realizado nos níveis inferiores pode ser maior que o trabalho realizado na raiz, para que você não tenha certeza de que a raiz domina.$\cos(n)$$n$

Deixe e b = 2 , de modo que T ( 2 N ) = N Σ k = 0 f ( 2 k ) . Para aplicar o caso 3, precisamos de f ( n ) = Ω ( n ϵ ) (para alguns ϵ > 0 ) e a condição de regularidade, f ( n / 2 ) ≤ ( 1 - δ ) $a = 1$$b = 2$

$$T(2^n) = \sum_{k=0}^n f(2^k).$$ $f(n) = \Omega(n^\epsilon)$$\epsilon > 0$ (para alguns$f(n/2) \leq (1-\delta) f(n)$$\delta > 0$$f(n) = n(2-\cos n)$ $$f(2^n) = 2^{2^{\lfloor \log_2 n \rfloor}} > 2^{2^{\log_2n-1}} = 2^{n/2}.$$ $n = 2^{m+1}-1$ $$T(2^n) = \sum_{k=0}^m \sum_{t=2^k}^{2^{k+1}-1} 2^{2^k} = \sum_{k=0}^m 2^{2^k+k} = \Theta(2^{2^m+m}), \quad f(2^n) = 2^{2^m}.$$ So it's not true that $T(2^n) = \Theta(f(2^n))$.

There is a more general theorem, Akra-Bazzi, in which the regularity condition is replaced by an explicit quantity that comes into the result.