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.

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

#### Earn Coins

Coins can be redeemed for fabulous gifts.