Discrete Mathematics |Gate-2012|
- The recurrence relation capturing the optional execution time of the Towers of Hanoi problem with nn discs is [GATE – 2012]
a. T (n) = 2T (n-2) + 2
b. T (n) = 2T (n-1) + n
c. T (n) = 2T (n/2) + 1
d. T (n) = 2T (n-1) + 1
Answer : d)