Answer the following question\'s with the provided Code: Question: What is the b
ID: 669069 • Letter: A
Question
Answer the following question's with the provided Code: Question: What is the big-O behavior of the function's time? How do you know?
#include <iostream>
using namespace std;
// Assuming n-th disk is bottom disk (count down)
void towerOfHanoi(int n, char sourcePole, char destinationPole, char auxiliaryPole)
{
// Base case (termination condition)
if(n == 0)
return;
// Move first n-1 disks from source pole
// to auxiliary pole using destination as
// temporary pole
towerOfHanoi(n-1, sourcePole, auxiliaryPole,
destinationPole);
// Move the remaining disk from source
// pole to destination pole
printf("Move the disk %d from %c to %c ", n,
sourcePole, destinationPole);
// Move the n-1 disks from auxiliary (now source)
// pole to destination pole using source pole as
// temporary (auxiliary) pole
towerOfHanoi(n-1, auxiliaryPole, destinationPole,
sourcePole);
}
int main(){
int number;
cout << "Enter the number of disks ";
cin >> number;
towerOfHanoi(number, '1', '3', '2');
}
Explanation / Answer
Let T(n) be the time to move n disks
T(n) = T(n-1) + T(n-1) + C, where c is a constant
T(1) = 1
T(n) = 2*T(n-1)
.. therefor T(n) approximately 2^n
Hence, T(n) = O(2n)