Analyze the following program which recursively solves the \"Towers of Hanoi\" p

Question

Analyze the following program which recursively solves the "Towers of Hanoi" problem for time complexity. Prove that the number of moves required is of the form O(2^n). void towersHanoi(int N, char S, char A, chair D) {if (N == 1) print "Move disc 1 from S rightarrow D^n; else {towersHanoi(N-1, S, A, D); print "Move disc N from S rightarrow D^n; towersHanoi(N-1, A, D, S);}} where N denotes the number of discs, and the three pegs are marked source (S), destination (D) and auxiliary (A), respectively.

Explanation / Answer

So,the first recursive call moves n-1 disks from "S" to "D" using "A". After this call, (n-1) disks are in "A" peg in order of size and the "S" peg contains the n'th disk or else say the largest one.

So, from now, move that disk from "S" to "D" peg. Then again in the second recursive call, move n-1 disk from "S" to "D" using "A" peg. Thus, after all these operations, "D" contains all disk in order of size.

Time Complexity:

Consider time taken for moving n disks is T(n)

In the given algorithm, there are 2 recursive calls made to move n-1 disk and a constant time to move disk from "S" to "D" . Let that constant be k1

Hence,T(n)=2 T(n-1) + k1

For T(0)= k2,be constant

T(1)= 2 T(0) + k1=2k2 + k1

T(2)=4k2 + 2k1 + k1

T(2)= 8k2 + 4k1 + 2k1 + k1

By observing the above statemnets, we get coefficient of k1 = 2n and k2= 2n-1

Hence, time complexity become O(2n)
and then copy paste

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---