- 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.
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\]
Passo 1
O enunciado nos dá um algoritmo recursivo que, para
, faz oito chamadas a
e depois executa um laço de
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
gera
subproblemas de tamanho
com
, e o trabalho não recursivo é dado por
Logo, a recorrência para o tempo de execução
é
com condição de contorno