Question

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.

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