Given the recurrence relations Tn for TowerOfHanoi Find th

Given the recurrence relations (T(n) = ...) for TowerOfHanoi. Find the time complexity of the algorithm, TowerOfHanoi, by solving T(n) in part (a).

Solution

The problem is divided into 2 parts, and a print statement.

So, the recurrence relation is: T(n) = 2 T(n-1) + 1. if n >= 1.

= 0 if n = 0.

And solving the reccurence to calculate the complexity is:

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

= 2(2T(n-2) + 1) + 1 = 2² T(n-2) + 2¹ + 2⁰

= 2²(2 T(n-3) + 1) + 2¹ + 2⁰ = 2³ T(n-3) + 2² + 2¹ + 2⁰

=

=

= 2ⁿ T(n-n) + 2^n-1 + 2^n-2 + ... + 2² + 2¹ + 2⁰ = 2^n-1 + 2^n-2 + ... + 2² + 2¹ + 2⁰ = 2ⁿ - 1.

Therefore, the number of steps required to solve the problem is: 2ⁿ - 1.