1. Suponha que, para entradas de tamanho n, você tenha de escolher um entre dois algoritmos.
    a) O algoritmo A resolve problemas dividindo-os em dois subproblemas de tamanho n-1, recursivamente resolve cada subproblema e então combina as soluções em tempo O(1).
    b) Algoritmo B resolve problemas dividindo-os em nove subproblemas de tamanho n/3, recursivamente resolve cada subproblema e então combina as soluções em tempo \mathrm{O}\left(\mathrm{n}^{2}\right).
    Qual o consumo de tempo desses algoritmos? Qual algoritmo é assintoticamente mais eficiente?

Passo 1

O enunciado pede para determinar a complexidade de dois algoritmos recursivos em função de n e depois compará-los assintoticamente. O conteúdo principal é resolver recorrências: para o algoritmo A usaremos expansão direta e, para o algoritmo B, o Teorema Mestre.

Passo 2

O algoritmo A satisfaz a recorrência
T_A(n) \;=\; 2\,T_A(n-1) \;+\; O(1).
Para resolver, seja c uma constante tal que o tempo de combinação seja c. Então
T_A(n) = 2T_A(n-1) + c.
Expansão por iterações:
\begin{aligned} T_A(n) &= 2\bigl(2T_A(n-2)+c\bigr) + c = 2^2T_A(n-2) + 2c + c,\\\ T_A(n) &= 2^3T_A(n-3) + 2^2c + 2c + c, \end{aligned}
e, após k passos,
T_A(n) = 2^kT_A(n-k) + c\sum_{i=0}^{k-1}2^i.
Escolhendo k=n e supondo T_A(0)=\Theta(1), obtemos
T_A(n) = 2^n\,\Theta(1) + c\,(2^n-1) = \Theta(2^n).

Passo 3

O algoritmo B satisfaz a recorrência
T_B(n) \;=\; 9\,T_B\bigl(\tfrac n3\bigr) \;+\; O(n^2).
Aplicando o Teorema Mestre:
  • a = 9, b = 3,
  • f(n) = \Theta(n^2),
  • n^{\log_b a} = n^{\log_3 9} = n^2.
    Como f(n) = \Theta\bigl(n^{\log_b a}\bigr), estamos no caso 2 do Teorema Mestre e então
T_B(n) = \Theta\bigl(n^{\log_3 9}\,\log n\bigr) = \Theta(n^2\log n).

Passo 4

Comparando
\Theta(2^n) versus \Theta(n^2\log n), fica claro que, para n grande, 2^n cresce muito mais rápido que qualquer polinomial vezes logaritmo. Portanto o algoritmo B é assintoticamente mais eficiente que o algoritmo A.

Resposta

T_A(n) = \Theta(2^n)
T_B(n) = \Theta(n^2\log n)
O algoritmo B é assintoticamente mais eficiente.

Exercícios relacionados