Carregando...
Carregando...
Considere a relação de recorrência dada por:
$S(n) = S\left(\frac{n}{3}\right) + \sqrt{n}$ , para $n \geq 3, \quad n = 3^m$ . Assinale a alternativa correta, com respeito à ordem de grandeza de $S(n)$ :
Explique melhor esta questão
Abre o Tutor com o enunciado e as alternativas já no campo — você revisa e envia.
Esta questão foi verificada por um de nossos administradores.
Observe que, pelo Teorema Mestre com os parâmetros $a=1, b=3, c=\frac{1}{2}$ , temos que $a = 1 <\sqrt{3} = 3^\frac{1}{2} = b^c$ . Dessa forma, segue que $S(n) = \Theta \left(\sqrt{n}\right)$ .