Question

In: Computer Science

) Write a recurrence relation of the following code and find the time complexity. void towerOfHanoi(int...

) 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);

}

Expert Solution

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ⁿ)

venereology answered 5 months ago

1. Mathematically analyze the given Recurrence Relation and find out the time complexity of the algorithm....

1. Mathematically analyze the given Recurrence Relation and find out the time complexity of the algorithm. T(n) = T(n-1)+1 , if n> 0 1 if n = 0

What is time Complexity each of the following function? 1- void function(int n) { for (int...

What is time Complexity each of the following function? 1- void function(int n) { for (int i=n/2; i<=n; i++) for (int j=1; j<=n/2; j++) for (int k=1; k<=n; k = k * 2) print ”Hello”; } 2- void function(int n) { for (int i=n/2; i<=n; i++) for (int j=1; j<=n; j = 2 * j) for (int k=1; k<=n; k = k * 2) print ”Hello”; } 3- void function(int n) { for (int i=1; i<=n; i++) for (int j=1;...

What is the ouput of the following code? void loop(int num) { for(int i = 1;...

What is the ouput of the following code? void loop(int num) { for(int i = 1; i < num; ++i) { for(int j = 0; j < 5; ++j) { cout << j; } } } int main() { loop(3); return 0; }

Consider the following code: void swap(int arr[], int i, int j) { int temp = arr[i];...

Consider the following code: void swap(int arr[], int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } void function(int arr[], int length) { for (int i = 0; i<length / 2; i++) swap(arr, i, (length / 2 + i) % length); } If the input to the function was int arr[] = { 6, 1, 8, 2, 5, 4, 3, 7 }; function(arr,8); What values would be stored in the array after calling the...

Write a method with the following header: public static void showGradeDistribution(int a, int b, int c,...

Write a method with the following header: public static void showGradeDistribution(int a, int b, int c, int d, int f) It should print a graph (using asterisks) for each of the letters entered in the reverse order of the parameter list and with a label. In addition, if A and B grades sum is equal or exceeds that of grades C and D and F, the message “Strong class!” should be displayed. For example a method call of: showGradeDistribution(5,7,4,4,3); Would...

Given the root C++ code: void sort() { const int N = 10; int...

Given the root C++ code: void sort() { const int N = 10; int x[N]; for(int i = 0; i < N; i++) { x[i] = 1 + gRandom-> Rndm() * 10; cout<<x[i]<<" "; } cout<<endl; int t; for(int i = 0; i < N; i++) { for(int j = i+1; j < N; j++) { if(x[j] < x[i]) { ...

a) Find the recurrence relation for the number of ways to arrange flags on an n...

a) Find the recurrence relation for the number of ways to arrange flags on an n foot flagpole with 1 foot high red flags, 2 feet high white flags and 1 foot high blue flags. b) solve the recurrence relation of part a

why my code for mergesort always wrong ? void Merge(vector<int>& data, int p, int q, int...

why my code for mergesort always wrong ? void Merge(vector<int>& data, int p, int q, int r) { int n1 = q - p + 1; int n2 = r - q; vector<int>left(n1); vector<int>right(n2); for(int i = 0; i < n1; i++) { left[i] = data[p + i]; } for(int j = 0; j < n2; j++) { right[j] = data[q+j+1]; } int i = 0; int j = 0; for(int k = p; k <= r; k++) { if(left[i]...

Please explain this code line by line void printperm(int *A,int n,int rem,int j) { if(n==1)...

Please explain this code line by line void printperm(int *A,int n,int rem,int j) { if(n==1) { for(int k=0;k<j;k++) cout<<A[k]<<" + "; cout<<rem<<"\n"; return; } for(int i=0;i<=rem;i++) { if(i<=rem) A[j]=i; printperm(A,n-1,rem-i,j+1); } }

Find and solve a recurrence relation for the number of ways to stack n poker

Find and solve a recurrence relation for the number of ways to stack n poker chips using red, white and blue chips such that no two red chips are together. Use your solution to compute the number of ways to stack 15 poker chips.