O limite assintótico de algoritmos recursivos pode ser estimado com boa precisão, através da modelagem via árvores de recursão. Para isso, os termo...

O limite assintótico de algoritmos recursivos pode ser estimado com boa precisão, através da modelagem via árvores de recursão. Para isso, os termos recursivos desempenham papel chave para o entendimento de como o algoritmo se comporta a cada iteração. Considerando que um algoritmo é modelado pela recursão T(n) = T(n/3) + T(2n/3) + cn, onde c é uma constante, analise as afirmativas a seguir. I. A árvore de recursão mostra que o custo de cada nível é cn. II. O limite assintótico inferior do algoritmo é Ω(nlog(n)). III. O caminho mais curto entre a raiz e um nó folha é log3(n). IV. O tamanho dos subproblemas decresce a um fator de 2/3. Está correto apenas o que se afirma em: Resposta: I, II e III. Resposta correta. Como os termos recursivos são divididos por 3, cada subproblema tem seu tamanho decrementado a um fator de 3. Porém, cada nível tem um acréscimo de cn termos, o que corresponde ao custo de cada nível. Para a definição do limite inferior do custo do algoritmo temos, cn(log3(n)) + 1 = cnlog3(n) = (c/log(3))nlog(n) = O(nlog(n)).

I. A árvore de recursão mostra que o custo de cada nível é cn.
II. O limite assintótico inferior do algoritmo é Ω(nlog(n)).
III. O caminho mais curto entre a raiz e um nó folha é log3(n).
IV. O tamanho dos subproblemas decresce a um fator de 2/3.
a) I, II e III.
b) I, II e IV.
c) I, III e IV.
d) II, III e IV.