This deals with C++ programming: Consider the following code fragment that uses

Question

This deals with C++ programming:

Consider the following code fragment that uses recursion to implement a function called process This() int process This(int n) { if(n == 0) return 1; else return process This(n/2 + 1);} Assume we call this function from a program with n = 5. i.e.. we call process This(5). What do you think is wrong with this code, and why? 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 0(2^n). void towersHanoi (int N, char S, char A, char D) { if(N 1) print "Move disc 1 from S rightarrow D"; else { towersHanoi (N-l, S, A, D); print "Move disc N from S rightarrow D"; towersHanoi (N-l, A, D, S);}} where N denotes the number of discs, and the three pegs an1 marked source (S). destination (D) and auxiliary (A), respectively.

Explanation / Answer

Answer1 : The first recursion code would result in infinite running.

for n=5, now n!=0 so we would again call processThis(5/2 +1). Being integer value returned so the output would be processThis(2+1) = processThis(3) .

for n=3, repeating same cycle we would have processThis(1+1) = processThis(2).

Now for n=2, repeating again we would have processThis(1+1) =processThis(2).

This would be an infinite loop until the stack memory goes out of the memory.

Answer2:

Now taking the worst case into picture and taking the actions in the else part of the code, so the number of the actions required are

towerhanoi(N-1,S,A,D)-> (n-1)

print "Move disc"-> 1

towerhanoi(N-1,A,S,D)->(n-2)

so the total number of actions required are (2n-3)+1=2(n-1)

so, T(n)=2(n-1)

now taking n-1 values, so T(n-1)=2(n-2)

similary taking n-2 values, so T(n-2)=2(n-3)

now, we can substitute the value of T(n-2) in T(n-1), so T(n-1) = 2*2(n-3)=4(n-3)

similary for T(n-3)=8(n-4), so we can relate as T(n)=2k(n-(k+1)),

So taking that into account we have complexity as O(2n)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.