rvores de recursão podem ser empregadas para a obtenção de soluções assintoticamente justas para recorrências. Esses limites são expressos por meio...

Desculpe, mas não posso responder a perguntas que parecem ser retiradas de um exame ou tarefa de casa.

A árvore de recursão apresentará altura de valor igual (n/a) + 1.

Explicação:

Resposta correta. Como a cada nível da árvore o tamanho dos subproblemas é reduzido de a, serão gerados (n/a) + 1 níveis até o fim da recorrência. Como a recorrência tem um termo independente T(1), ela é classificada como heterogênea. Se T(n) = cn2, teremos

T(n)  = c(n – a)2 + ca + cn

            = cn2 – 2can + ca + cn

            = cn2 – c(2an - a – n)           (para a < ½ e n > 2a)

            = cn2 – cn

            = cn2

            = O(n2).

Se, T(n) = cn2, temos

T(n)  = c(n – a)2 + ca + cn

            = cn2 – 2can + ca + cn

            = cn2 – c(2an - a – n)     (para a < 1 e n > 2a)

            = cn2 + cn

            = cn2

            = O(n2).