Perform complexity analysis for the algorithm by

1) find the recurrence equation;

(2) solve the recurrent equation and

(3) conclude on the complexity class for the algorithm by a proof.

Include how the recurrence equation is derived, how it is solved and prove the asymtotic complexity.

Analyze the number of disk moves in terms of n

void TowersOfHanoi(int n, int x, int y, int z) // n>= 0 {

// Move n disks from tower x to tower y. // Use tower z for intermediate storage.

if (n > 0) {

TowersOfHanoi(n-1, x, z, y);

cout << "Move disk from " << x << " to " << y << endl;

TowersOfHanoi(n-1, z, y, x);}

}