[Enunciado]
Queremos obter cotas (superior e inferior)
para a solução da
recorrência (E.1).
Queremos fazer isso,
por interpolação
,
a partir das cotas que já temos para a solução
da recorrência (D.1).
Convém lembrar que (E.1) é a recorrência
T(n) = 2 T(⌊n/2⌋) + 7n + 2
para n = 2, 3, 4, 5, etc. com valor inicial T(1) = 1. Já (D.1) é a recorrência
F(N) = 2 F(N/2) + 7N + 2
para N = 21, 22, 23, 24, etc. com valor inicial F(1) = 1. É claro que (D.1) é a restrição de (E.1) às potências de 2 e portanto F(N) = T(N) sempre que N é uma potência de 2.
Como já mostramos, a solução F de (D.1) satisfaz as cotas
| 6N lg N ≤ F(N) ≤ 8N lg N | (D.3) |
para toda potência N de 2 a partir de 23. Gostaríamos de estender essas cotas à solução T de (E.1). É preciso mostrar antes que T é crescente.
Teorema 1: A solução de (E.1) é crescente.
Prova: Basta mostrar que T(n) ≤ T(n + 1) para todo natural positivo n. É fácil verificar que T(1) = 1 ≤ 18 = T(2). Agora tome n ≥ 2. Se n é par então ⌊n/2⌋ = n/2 = ⌊(n+1)/2⌋ e portanto
| T(n) | = | 2T(⌊(n+1)/2⌋) + 7n + 2 |
| < | 2T(⌊(n+1)/2⌋) + 7(n + 1) + 2 | |
| = | T(n + 1). |
Suponha agora que n é ímpar. Então ⌊n/2⌋ + 1 = (n+1)/2 = ⌊(n+1)/2⌋. Podemos supor, a título de hipótese de indução, que T(⌊n/2⌋) ≤ T(⌊n/2⌋ + 1). Então
| T(n) | = | 2T(⌊n/2⌋) + 7n + 2 |
| ≤ | 2T(⌊n/2⌋+1) + 7n + 2 | |
| = | 2T(⌊(n+1)/2⌋) + 7n + 2 | |
| < | 2T(⌊(n+1)/2⌋) + 7(n + 1) + 2 | |
| = | T(n + 1) , CQD. |
Teorema 2: T(n) ≤ 32 n lg n para todo natural n a partir de 8.
Prova: Seja k o número ⌈lg n⌉ e N o número 2k. Então N/2 < n ≤ N e n ≤ N < 2n. Como T é crescente (teorema 1), temos T(n) ≤ T(N), e assim as cotas (D.3) garantem que
| T(n) | ≤ | T(N) |
| = | F(N) | |
| ≤ | 8 N lg N | |
| < | 8 (2n) lg (2n) | |
| = | 16 n (1 + lg n) | |
| ≤ | 16 n (2 lg n) | |
| = | 32 n lg n, CQD. |
Teorema 3: T(n) ≥ n lg n para todo natural n a partir de 8.
Prova: Seja k o número ⌊lg n⌋ e N o número 2k. Então N ≤ n < 2N. Como T é crescente (teorema 1), T(n) ≥ T(N) e portanto
| T(n) | ≥ | T(N) |
| = | F(N) | |
| ≥ | 6 N lg N | |
| > | 6 (n/2) lg (n/2) | |
| = | 3 n (lg n − 1) | |
| ≥ | 3 n (lg n)/2 | |
| > | n lg n, CQD. |