1. O limite \Omega(n . \log n) é uma boa solução para a relação T(n)=T\left(\frac{n}{3}\right)+T\left(\frac{2 n}{3}\right)+n ? Argumente usando o método iterativo.

Passo 1

O enunciado fornece a recorrência
T(n) = T\!\Bigl(\frac{n}{3}\Bigr) + T\!\Bigl(\frac{2n}{3}\Bigr) + n
e pede para verificar se \Omega(n\log n) é um limite assintótico válido para T(n). Vamos usar o método iterativo (árvore de recursão) para estimar o custo total e ver que T(n)\in\Omega(n\log n).

Passo 2

Desenhemos a árvore de recursão. No nível 0 (raiz) temos custo
\text{nível }0:\quad n.í
Esse nó gera dois filhos de tamanhos n/3 e 2n/3.

Passo 3

No nível 1, os dois nós custam respectivamente n/3 e 2n/3, totalizando
\text{nível }1:\quad \frac{n}{3} + \frac{2n}{3} = n.í
Em geral, em cada nível i a soma dos tamanhos dos subproblemas é sempre
\sum_{\text{nós no nível }i} \text{tamanho} = n,óí
pois a partição sempre adiciona até n.

Passo 4

Precisamos agora do número de níveis h até chegar a subproblemas de tamanho constante. A maior profundidade vem da cadeia que divide sempre pela mesma fração. Podemos olhar só para a subrecorrência maior T(2n/3). Após h divisões temos tamanho
n\Bigl(\tfrac{2}{3}\Bigr)^{h} \approx 1 \quad\Longrightarrow\quad \Bigl(\tfrac{2}{3}\Bigr)^{h} = \frac{1}{n} \quad\Longrightarrow\quad h = \log_{3/2}n = \Theta(\log n).

Passo 5

Cada um dos h+1 níveis dá custo n. Ignorando o custo das folhas (constante), o total da árvore é
T(n) \approx n + n + \dots + n \quad\text{(em }h+1\text{ níveis)} \quad\Longrightarrow\quad T(n) = n\,(h+1) = \Theta\bigl(n\log n\bigr).í
Em particular, isso mostra T(n)\in\Omega(n\log n).

Resposta

Sim. O método iterativo mostra que
T(n)=\Theta(n\log n),
logo \Omega(n\log n) é de fato um limite assintótico válido para T(n).

Exercícios relacionados