GATE 2012 CS (CS1) – Question 26
Which recurrence gives optimal Towers of Hanoi time for n disks?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (D) $T(n)=2T(n-1)+1$
Explanation
Move n−1 disks to the spare peg, move the largest disk once, and move those n−1 disks onto it. Thus $T(n)=2T(n-1)+1$, D, with T(0)=0. The solution is 2ⁿ−1 moves.