GATE CSE 2015 Set 2 | Question: 11

Question

Consider the following C function.

int fun(int n) {
    int x=1, k;
    if (n==1) return x;
    for (k=1; k<n; ++k)
        x = x + fun(k) * fun (n-k);
    return x;
}

The return value of $fun(5)$ is ______.

Comments

Here if we use k++ instead of ++k what was the ans ?

---

Can anyone help me what is the time complexity of this function??

is it O(2^n).

---

recursive Equation is

f(n)=n+2*[f(n-1)+f(n-2)+...f(1)]

If you solve this

Complexity will be O(3^n)

Answer 1

Answer is 51

Explanation:

By mathematical induction,solve this from smaller value to bigger value

fun(1) → fun(2) → fun(3) → fun(4) → fun(5)

For n=1,it check if(1=1).The condition is true so it return 1;

For n=2,The if condition fails then it execute for loop for k<2 times

              For k=1,

              x=1+fun(1)*fun(2-1); => 1+fun(1)*fun(1) => 1+1*1 => 2

              it returns x=2 so fun(2)=2

For n=3,The if condition fails then it execute for loop for k=1,2

              For k=1,

              x=1+fun(1)*fun(3-1); => 1+fun(1)*fun(2) => 1+1*2 => 3

              For k=2,

              x=3+fun(2)*fun(3-2); => 3+fun(2)*fun(1) => 3+2*1 => 5

              It return x =5 => fun(3)=5

For n=4,The if condition fails then it execute for loop for k=1,2,3

              For k=1,

              x=1+fun(1)*fun(4-1); => 1+fun(1)*fun(3) => 1+1*5 => 6

              For k=2,

              x=6+fun(2)*fun(4-2); => 6+fun(2)*fun(2) => 6+2*2 => 10

              For k=3,

              x=10+fun(3)*fun(4-3); => 10+fun(3)*fun(1) => 10+5*1 => 15

              It return x =15 => fun(4)=15

For n=5,The if condition fails then it execute for loop for k=1,2,3,4

              For k=1,

              x=1+fun(1)*fun(5-1); => 1+fun(1)*fun(4) => 1+1*15 => 16

              For k=2,

              x=16+fun(2)*fun(5-2); => 16+fun(2)*fun(3) => 16+2*5 => 26

              For k=3,

              x=26+fun(3)*fun(5-3); => 26+fun(3)*fun(2) => 26+5*2 => 36

              For k=4,

              x=36+fun(4)*fun(5-4); => 36+fun(4)*fun(1) => 36+15*1 => 51

              It return x =51 => fun(5)=51.

Answer 2

c is the correct option