MO417 - Questão para a porva oral

MO417 - Questão para a porva oral

Número: 2013-012

Enunciado: Dada a seguinte função recursiva:

        Function (n)

              if (n ≤ 1)

                    PARAR

              else

                    Ativar processo X

                    Function (n/2)

                 

Sendo T(n) o número de ativações do processo X, a fórmula de recorrência que representa esta função é:

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

Podemos afirmar que:

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

b) O processo x será ativado lg n vezes.

c) O processo x será ativado n lg n vezes.

d) O processo x será ativado 2ⁿ vezes.

e) NDA

Ideia original de: Lucas Oliveira Batista