MO417 - Questão para a prova oral

MO417 - Questão para a prova oral

Número: 2013-011

Enunciado: Considere o algoritmo abaixo para a resolução do problema Torre de Hanoi.

Algoritmo Hanoi (n, ori, des, aux)
 se n = 1
      então “move pino” de ori para des
 senão Hanoi (n − 1, ori, aux, des)
      “move pino” de ori para des
      Hanoi (n − 1, aux, des, ori)

A seguir, considere a recorrência para este problema:

T(n)=1                 para n=1
T(n)=2T(n-1)+1   para n>1

É correto afirmar que:

a. T(n)=Θ(2ⁿ)
b. T(n)=Θ(n²)
c. T(n)=Θ(n lg n)
d. T(n)=Θ(n² lg n)
e. NDA

Ideia original de: Jacqueline Midlej do Espírito Santo