Question

1. ) Write a recurrence relation of the following code and find the time complexity.

void towerOfHanoi(int n, char from_rod,

                    char to_rod, char aux_rod)

{

    if (n == 1)

    {

        cout << "Move disk 1 from " << from_rod << " to " << to_rod<<endl;

        return;

    }

    towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);

    cout << "Move disk " << n << " from " << from_rod << " to " << to_rod << endl;

    towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);

}

Answer 1

Recurrence relation for the following code is:

Let t(n) be number of moves the function takes for a n-dist tower.

The base case is when n=1 which requires only 1 move.

In other cases the number of moves required is 1+t(n-1)+t(n-1).

Therefore,

t(n ) =1 if n=1

=1+2(n-1) if(n>1)

solving the equation:

Time complexity is O(2ⁿ)