1. Calcule o tempo de um algoritmo cuja relação de recorrência é T(n)=T(\sqrt[3]{n})+\Theta(1).

Passo 1

O enunciado dá a recorrência
T(n)=T\bigl(n^{1/3}\bigr)+\Theta(1)
e pede o tempo assintótico. O conteúdo usado será expansão repetida até o caso base e contagem do número de níveis de recursão.

Passo 2

Definimos n_{0}=n e, em geral,
n_{k}=(n_{k-1})^{1/3}.
Por indução obtém-se
n_{k}=n^{1/3^{\,k}}.
Em cada nível de recursão há custo \Theta(1).

Passo 3

Para achar o número de níveis m até atingir o caso base constante, exigimos
n_{m}=n^{1/3^{\,m}}=O(1).
Tomando logaritmo natural,
\frac{1}{3^{\,m}}\ln n = O(1) \quad\Longrightarrow\quad 3^{\,m}=\Theta(\ln n) \quad\Longrightarrow\quad m=\Theta\bigl(\log_{3}(\ln n)\bigr)=\Theta(\log\log n).

Passo 4

Cada um dos m níveis custa \Theta(1), logo
T(n)=\sum_{i=0}^{m-1}\Theta(1)=\Theta(m)=\Theta(\log\log n).

Resposta

\Theta(\log\log n)

Exercícios relacionados