GATE CS 2012 Q16 — Asymptotic Worst Case Time and Space Complexity

To solve the Towers of Hanoi problem with $n$ discs from a source peg to a destination peg using an auxiliary peg, we follow these optimal steps:

1. Step 1: Move the top $n-1$ discs from the source peg to the auxiliary peg. This requires $T(n-1)$ moves.
2. Step 2: Move the largest ($n$-th) disc directly from the source peg to the destination peg. This requires exactly $1$ move.
3. Step 3: Move the $n-1$ discs from the auxiliary peg to the destination peg. This requires another $T(n-1)$ moves.

Summing the moves for these steps, the total number of moves $T(n)$ is given by:

With the base case $T(1) = 1$ (or $T(0) = 0$).

Therefore, the correct recurrence relation is $T(n) = 2T(n-1) + 1$, which corresponds to Option D.