Multiple choice

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

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

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

  3. T(n) = 2T(n/2) + 1

  4. T(n) = 2T(n -1) + 1
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

Let the three pegs be A, B and C, the goal is to move n pegs from A to C using peg B The following sequence of steps are executed recursively 1.move n - i discs from A to B. This leaves disc n alone on peg A --- T(n - 1) 2.move disc n from A to C 1 3.move n - i discs from B to C so they sit on disc n T(n - 1) So, T(n) = 2T(n - 1) + 1

Keep practicing — related questions