in Algorithms edited by
20,792 views
62 votes
62 votes

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 ______.

in Algorithms edited by
20.8k views

4 Comments

Here if we use k++ instead of ++k what was the ans ?
0
0
Can anyone help me what is the time complexity of this function??

is it O(2^n).
0
0
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)
0
0

12 Answers

130 votes
130 votes
Best answer

$\text{fun}(1) = 1$;

$\text{fun}(2) = 1 + \text{fun}(1) * \text{fun}(1) = 1 + 1 = 2$;

$\text{fun}(3) = 1 + \text{fun}(1) * \text{fun}(2) + \text{fun}(2) * \text{fun}(1) = 5$;

$\text{fun}(4) = 1 + \text{fun}(1) * \text{fun}(3) + \text{fun}(2) * \text{fun}(2) + \text{fun}(3) * \text{fun}(1)$
$\qquad = 1 + 5 + 4 + 5 = 15$;

$\text{fun}(5) = 1 + \text{fun}(1) * \text{fun}(4) + \text{fun}(2) * \text{fun}(3) + \text{fun}(3) * \text{fun}(2) + \text{fun}(4) * \text{fun}(1)$
$\qquad = 1 + 15 + 10 + 10 + 15  = 51$;


More formal way:

The recurrence relation is

$f(n) = \begin{cases} 1, n = 1 \\ 1 + \sum_{i=1}^{n-1} f(i) \times f(n-i), n > 1 \end{cases}$

$f(1) = 1$

$f(2) = 1+ f(1).f(1)$
$\qquad = 1 + 1.1 = 2$

$f(3) = 1 + f(1). f(2) + f(2).f(1)$
$\qquad= 1+ 1.2 + 2.1 = 5$

$f(4) = 1 + f(1).f(3) + f(2).f(2) + f(3).f(1)$
$ \qquad= 1+ 1.5 + 2.2 + 5.1 = 15$

$f(5) = 1 + f(1).f(4) + f(2).f(3) + f(3). f(2)+ f(4).f(1)$
$\qquad = 1 + 1.15 + 2.5 + 5.2 + 15.1 = 51$

edited by
by

4 Comments

edited by
Amazing explanation...
0
0
I was trying solving this in top down manner but bottom up approach is quite easier and less time consuming.
5
5

That’s the essence of Dynamic Programming @Aditya_

2
2
30 votes
30 votes
fun(1) =1
 
fun(2) : x=1+fun(1)*fun(1)
             x=1+1*1
             x=2
           fun(2) = 2
 
fun(3) : x = x+fun(1)*fun(2)
            x= 1+1*2
            x= 3
 
            x= 3+fun(2)*fun(1)
            x= 3+2*1
            x= 5
            fun(3) = 5
 
fun(4) : x = x+fun(1)*fun(3)
            x= 1+1*5
            x= 6
 
           x = x+fun(2)*fun(2)
           x= 6+2*2
           x= 10
 
           x = x+fun(3)*fun(1)
           x= 10+5*1
           x= 15
 
fun(5): x = x+fun(1)*fun(4)
           x= 1+1*15
           x= 16
 
           x = x+fun(2)*fun(3)
           x= 16+2*5
           x= 26
 
           x = x+fun(3)*fun(2)
           x= 26+5*2
           x= 36
 
          x = x+fun(4)*fun(1)
          x= 36+15*1
          x= 51

2 Comments

Gd presentation ...
0
0
Great explanation.i was confused at x=x + f(k)* f(n-k) but now you cleared by showing intermediate steps as we are utilising updated x value for other iteration in same for loop.
0
0
18 votes
18 votes

Dont use tree method of recursion when they asked embedded function call inside loop . Better to do step by step like below:-

3 Comments

@rajesh nicely explain  but i m having doubt is it ++k and k++ gives the same value if yes plz tell me little bit about it . bcz i m thinking that we are not assign the value of k thts why its not making any effect on either k++ or ++k  ami rt??
0
0
k++ or ++k doesn't affrect ans.
0
0
superb sir ji.....
0
0
8 votes
8 votes
don't use tree method of recursion when they asked embedded function call inside loop . let's  do step by step

f(1) ⇒1

f(2) ⇒ x=1

          1 + f(1)*f(1) = 2

f(3) ⇒ x=1

          k=1 : 1 + f(1)*f(2) = 3

          k=2 : 3 + f(2)*f(1) = 5

f(4) ⇒ x=1

         k=1 : 1 + f(1)*f(3) = 6

         k=2 : 6 + f(2)*f(2) = 10

         k=3 : 10 + f(3)*f(1) = 15

f(5) ⇒ x=1

         k=1 : 1 + f(1)*f(4) = 16

         k=2 : 16 + f(2)*f(3) = 26

         k=3 : 26 + f(3)*f(2) = 36

         k=4 : 36 + f(4)*f(1) = 51

so  51

1 comment

yes 51
0
0
Answer:

Related questions