MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: Dada a seguinte função recursiva:

        Function (n)

              if (n ≤ 1)

                    PARAR

              else

                    Ativar processo X

                    Function (n/2)

                 

A fórmula de recorrência que representa esta função é:

       
          T(n) = 1 + T(n/2),       n>1
          T(1) = 0

Sendo T(n) o número de ativações do processo X, podemos afirmar que:

a) A recorrência não pode ser resolvida pelo método mestre, pois não existe a constante “a”.

b) T(n) = Θ (lg n), logo o processo x será ativado lg n vezes.

c) T(n) = Θ (n lg n), logo o processo x será ativado n lg n vezes.

d) T(n) = Θ (2ⁿ), logo o processo x será ativado 2ⁿ vezes.

e) NDA

Ideia original de: Lucas Oliveira Batista