GATE CS 2012 Q.16 (CS Q.16): Divide and Conquer

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with $n$ discs is

$T(n) = 2T(n - 2) + 2$

$T(n) = 2T(n - 1) + n$

$T(n) = 2T(n/2) + 1$

$T(n) = 2T(n - 1) + 1$

Official answer and solution

Solution

Formulate the recurrence relation for moving $n$ disks between three pegs in the classic Towers of Hanoi puzzle.

To transfer $n$ disks from the source peg $A$ to the target peg $C$ using auxiliary peg $B$ :

Step 1: Recursively move the top $n - 1$ disks from peg $A$ to peg $B$ . This requires $T(n - 1)$ optimal moves.
Step 2: Move the single largest disk ( $n$ -th disk) directly from peg $A$ to peg $C$ . This takes exactly 1 move.
Step 3: Recursively move the $n - 1$ disks from peg $B$ to peg $C$ using peg $A$ . This requires $T(n - 1)$ optimal moves.

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

with base condition $T(1) = 1$ .

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.