Project ForgeAlgorithms
Complexity Analysis
GATE 2012
Easy
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
- AT(n) = 2T(n−2) + 2
- BT(n) = 2T(n−1) + n
- CT(n) = 2T(n/2) + 1
- T(n) = 2T(n−1) + 1
Explanation
Solving Towers of Hanoi for n discs means moving the top n−1 discs to the spare peg (T(n−1) moves), moving the largest disc (1 move), then moving the n−1 discs back on top of it (another T(n−1) moves): T(n) = 2T(n−1) + 1.
Source: GATE CS 2012 (2012)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.