Question

Below is C code and Python code for an algorithm. C code: void foo( int n,...

Below is C code and Python code for an algorithm.

C code:

void foo( int n, int A, int B, int C ) {

if( n==1 ) {

printf("%d to %d\n",A,B);

return;

}

foo( n-1, A, C, B );

printf("%d to %d\n",A,B);

foo( n-1, B, C, A );

Python code:

def foo(n , A, B, C):

if n==1:

print A, "to", B

return

foo(n-1, A, C, B)

print A, "to", B

foo(n-1, B, C, A)

Let Hn be the number of times the printing function is executed. Assume n ≥ 1. Give a recurrence equation and an initial value for Hn and solve it. Note, you do not need to know what the code is doing to answer this question.

Homework Answers

Answer #1

Here the function foo() is called twice and length of array is decreased by 1 in each case.

If originally time required when size of array was n was T(n) , then time required when size of becomes n-1 is T(n-1).

Also when n==1, we print a single statement which takes a constant amount of time 1.

Also there is a print statement between the two function call.

So total amount of extra time is 2 which is again constant.

So the recurrence relation is :

T(n) = 2T(n-1) +2

Where T(1) =1.

If you have any questions comment down. Please don't simply downvote and leave. If you are satisfied with answer, please? upvote thanks

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Consider the following recursive algorithm Algorithm S(n) if n==1 return 1 else return S(n-1) + n*n*n...
Consider the following recursive algorithm Algorithm S(n) if n==1 return 1 else return S(n-1) + n*n*n 1)What does this algorithm compute? 2) Set up and solve a recurrence relation for the number of times the algorithm's basic operation is executed. 3) How does this algorithm compare with the non-recusive algorithm for computing thius function in terms of time efficeincy and space effeciency?
How can i make this lunix code print 3 numbers in reverse it must be in...
How can i make this lunix code print 3 numbers in reverse it must be in printStars format and no loops Here is the code i have but can figure out how to reverse the numbers #include<stdio.h> void printStars(int n) { if (n>0){ printf(""); printStars(n-1); } } int main() { int n; int b; int c; printf("Enter 3 numbers to reverse "); scanf("%d",&n,&b,&c); printf("your reversed numbers are %d",n); printStars(n); return 0;
Translate C code into MIPS. Do not include an exit syscall int proc1( int a, int...
Translate C code into MIPS. Do not include an exit syscall int proc1( int a, int b ) { if ( proc2( a, b ) >= 0 ) return 1; else return -1; } int proc2( int a, int b ) { return (a*10) & (b*10); } int main() { int a = 9; int b = -10; int c = a + b + proc1( a, b ); printf("%d\n", c ); return 0; }
#include <stdio.h> extern unsigned long long sum(unsigned int *array, size_t n); int main(void) { unsigned int...
#include <stdio.h> extern unsigned long long sum(unsigned int *array, size_t n); int main(void) { unsigned int array[] = { 1, 1, 1, 3 }; unsigned long long r = sum(array, sizeof(array) / sizeof(*array)); printf("Result is: %llu (%s)\n", r, r == 6 ? "correct" : "incorrect"); return 0; } Complete the code for the line that calls the sum function. Write the sum function.
What is output? #include <stdio.h> void CheckValue(int* pointVar1, int* pointVar2) {       if (pointVar1 == NULL...
What is output? #include <stdio.h> void CheckValue(int* pointVar1, int* pointVar2) {       if (pointVar1 == NULL && pointVar2 == NULL) {       printf("Pointer is null\n");    }    else if (*pointVar2 > *pointVar1) {       printf("%p\n", *pointVar2);    }    else if (*pointVar1 > *pointVar2) {       printf("%p\n", *pointVar1);    } } int main() {    int num1 = 5;    int num2 = 9;       CheckValue(&num1, &num2);           return 0; } a. 0 b. 5 c. 9 d. Pointer is null e....
I am experimenting with pointers in C. I wrote this code. int i1; int i2 =...
I am experimenting with pointers in C. I wrote this code. int i1; int i2 = 50; int *intptr1; int *intptr2; intptr1 = &i1; intptr2 = &i2; intptr1 = intptr2; printf("\nvalue of intptr1: %d\n", *intptr1); /*prints 50*/ dubptr1 = (double *)intptr1; printf("\nvalue of dubptr1: %f\n", *dubptr1); /*prints 0.0000*/ I would have expected the last statement to print 50.0000. Is it actually supposed to print 0.0000 or did I make a mistake somewhere and if I did please help me understand...
Consider the following insertion sort algorithm. void insertion_sort(element a[], int n) // Put a[0]..a[n-1] into ascending...
Consider the following insertion sort algorithm. void insertion_sort(element a[], int n) // Put a[0]..a[n-1] into ascending order by insertion sort. { for (int k = 1; k < n; k++) { // At this point, a[0]..a[k-1] are already in order. // Insert a[k] where it belongs among a[0]..a[k]. You need to write code for this insertion as the body of the for-k loop. }//endfor k } a) Write the code for the body of the for-k loop to complete the...
a. Design a non-recursive algorithm for computing an (discussed in the class). What is the basic...
a. Design a non-recursive algorithm for computing an (discussed in the class). What is the basic operation? How many times is the algorithm’s basic operation executed? b. Using an = a*an-1 (discussed in the class) to design a recursive algorithm for computing an . What is the basic operation? Set up and solve a recurrence relation for the number of times that algorithm's basic operation is executed. c. Using an = a*(a(n-1)/2) 2 (n is odd integer) and an =...
For each part labeled P(n), there is a warning/error/problem that goes with it. Write down what...
For each part labeled P(n), there is a warning/error/problem that goes with it. Write down what the issue was in the `Error:` section of each problem. And fix the code to make it work. // P0 #include <stdio.h> #include <stdlib.h> /* Error: */ void fib(int* A, int n); int main(int argc, char *argv[]) { int buf[10]; unsigned int i; char *str; char *printThisOne; char *word; int *integers; int foo; int *bar; char *someText; // P1 for (i = 0; i...
C PROGRAMMING LANGUAGE The following code written in C programming language was run and displays 997705320....
C PROGRAMMING LANGUAGE The following code written in C programming language was run and displays 997705320. Explain why and how this program outputs this number. int main(void) { int a = 5, b =20; int* ptr = &a; int** ptr2 = &ptr; printf("%d\n", ((int)*ptr * (int)*ptr2)); return 0; }
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT