1. Considere o seguinte algoritmo.
function \(\operatorname{ALGO}(\mathrm{n})\)
    if \(n \leq 1\) then
        return 1
    for \(i=1, \ldots, 8\) do
        \(z=\operatorname{ALGO}(n / 2)\)
    for \(i=1, \ldots, n^{3}\) do
\[z=0\]
a. Escreva a recorrência para o algoritmo.

Passo 1

O enunciado nos dá um algoritmo recursivo que, para n>1, faz oito chamadas a \mathrm{ALGO}(n/2) e depois executa um laço de n^3 iterações com custo constante por iteração. O conteúdo aqui é formulação de recorrência para análise de algoritmos recursivos.

Passo 2

Cada chamada de tamanho n gera a=8 subproblemas de tamanho n/b com b=2, e o trabalho não recursivo é dado por
f(n)=\Theta(n^3).
Logo, a recorrência para o tempo de execução T(n) é
T(n)=8\,T\bigl(n/2\bigr)+\Theta(n^3),\quad n>1,
com condição de contorno
T(n)=\Theta(1),\quad n\le1.

Resposta

T(n)=8\,T\bigl(n/2\bigr)+n^3,\quad T(n)=1\text{ para }n\le1.

Exercícios relacionados