Use Mathematical Induction to prove that the computational complexity of the Tow

Question

Use Mathematical Induction to prove that the computational complexity of the Tower of Hanoi algorithm below is 2^n - 1. Show each of the following steps: (a) verification for the base case, (b) statement of the induction hypothesis, (c) the induction step, and (d) deduction or conclusion based on the Mathematical Induction.

Tower of Hanoi code:

#include <iostream>

using namespace std;

int m=0; // count number of moves in this global variable.

void tower(int n, int s, int f, int t){

       if(n==0) return;

       tower(n-1,s,t,f);

       cout << "Move No. " << ++m << ":    Move one top disk from " << s << " to " << f << " . ";

       tower(n-1,t,f,s);

       return;

}

void main( ) {

       int n;

       cout << "Enter number of entries n. ";

       cin >> n;

       if ( (n<=0) || (n>12) ) {

             cout << "n out of bounds [ 1..12]. ";

             return;

       }

       m = 0;

       tower(n,1,2,3);

       cout << " type any character to quit ";

       char c;

       cin >>c;

}

// ESE 344, SBU, Murali Subbarao

// Example of recursion

// GCD greatest common divisor program

#include <iostream>

using namespace std;

int gcd(int m, int n)     // function definition

{   

       if ((m <= 0) || (n <= 0)) return 0;

       if (m%n == 0) return n;

       else return gcd(n, m%n);

}

void main()

{

      

       int m1, n1; char c;

       do {

             cout << " GCD :   Enter two integers greater than or equal to 1 : ";

             cin >> m1 >> n1;

             cout << "GCD of " << m1 << ", " << n1 << " is : " << gcd(m1, n1) << endl << endl;

             cout << "Another input pair ? Type y/n : ";

             cin >> c;

             cout << endl;

       } while (c == 'y');

       return;

}

// Binary search example.

// Prof. Murali Subbarao

#include <iostream>

using namespace std;

#include <cstdlib>   // for rand(), srand()

#include <ctime>     // for time()

#include <math.h>    // for sqrt()

int countn = 0;

int BinarySearch(int a[], int l, int h, int k)

{   int mid;

    countn++;

       if(l>h) return -h;

       mid= (l+h)/2;

       if(k==a[mid]) return mid;

       else if (k<a[mid]) return BinarySearch(a,l,mid-1,k);

       else return BinarySearch(a,mid+1,h,k);

}

void sort(int a[], int n) {

       int i,j;

             //sort

             for(i=0;i<n;i++) {

                    int tmpmin=a[i];

                    for(j=i+1;j<n;j++) {

                           if(tmpmin>a[j])

                           { tmpmin = a[j];

                                     a[j]=a[i];

                                     a[i]= tmpmin;

                                  }

                           }

                    }

}

void main( ) {

       int n,k;

       int a[1000]; // array to store data

       cout << "Enter 0 for simulation input, and 1 for external input. ";

       cin >>k ;

       if (k != 1) k=0;

       // read data

       cout << "Enter number of entries n. ";

       cin >> n;

       if ( (n<=0) || (n>1000) ) {

             cout << "n out of bounds. ";

             return;

       }

    srand((unsigned int) time(NULL));// seed rand() with system time

       int i;

    for(i=0;i<n;i++) { // assumes legal input

             int x;

             if (k == 1) {

                    cout << " Enter next data : ";

                    cin >> x; // you can read from a file with this

             }

             else

                    x= (int) (rand()%10000); // limit data to 0 to 9999.

             cout <<" " << x ;

             a[i] = x;

       }

       cout << endl;

       sort(a,n);

       for (i = 0; i<n; i++) { //

             cout << " " << a[i];

       }

       cout << endl;

       cout << "Enter number or key to search for OR -1 to exit : ";

       cin >> k;

    while (k>0) {

             int pos;

             int l,h;

             l=0; h=n-1;

             countn =0; // number or calls, globl variable

             pos = BinarySearch(a,l,h,k);

             cout << "Position : " << pos << " Count: " << countn << endl;

             cout << "Enter number or key to search for OR -1 to exit : ";

             cin >> k;

       }

      

}

Explanation / Answer

Solution:

Generally, In Tower of Hanoi problem, we are given three towers and some discs are placed in a tower which is called as source tower in order as larger ones are at the bottom and the smaller one is on the top and all the discs are placed in that order, which means no larger disc will be placed on the smaller disc.

Now we have to switch the tower which is known as destination tower destination tower in such a manner so that there is no violation of the stated rule, we have the third tower which is called spare tower through which we have to accomplish our objective.

Proof:

The base case is when n=1; this means that when we have only one disk in the source tower then only one move needs to be done which is shifting that disk to destination tower.

we can write is T(1)= 1,

in other cases when the disks is more than 1 (n>1)

then n-1 disks needed to move to spare tower and then they move n-1 disks to the destination tower again

So recurrence relation T(n)= 2T(n-1) + 1

Induction:

after observing the pattern, we can conclude that

T(n) = 2n - 1.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

T(1)= 1 T(2)=2T(1) + 1 =3 T(3)=2T(2) + 1 =7 T(4)=2T(3) + 1 =15 T(5)=2T(4) + 1 =31

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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