Select the correct recurrence relation for Tower of Hanoi?ans.T(n)= 2T(n-1)+2T(n)= 2T(n-2)+2T(n)= 2T(n)+1T(n)= 2T(n-1)+1 Previous Marked for Review Next

The correct recurrence relation for Tower of Hanoi is T(n) = 2T(n-1) + 1.

Here's why:

The Tower of Hanoi problem is a classic example of recursion. The problem can be solved by breaking it down into smaller subproblems.

1. Move the top n-1 disks from the source peg to an auxiliary peg.
2. Move the nth disk from the source peg to the target peg.
3. Move the n-1 disks from the auxiliary peg to the target peg.

Each of these steps is a recursive call, and each call has a cost. The cost of moving n-1 disks is T(n-1). The cost of moving the nth disk is constant, let's say 1.

So, the total cost T(n) is the cost of moving n-1 disks twice (once from the source peg to the auxiliary peg, and once from the auxiliary peg to the target peg), plus the cost of moving the nth disk.

This gives us the recurrence relation T(n) = 2T(n-1) + 1.