GATE CSE 1997 | Question: 15

Question

Consider the following function.

Function F(n, m:integer):integer;
begin
    if (n<=0) or (m<=0) then F:=1
    else
      F:F(n-1, m) + F(n, m-1);
end;

Use the recurrence relation  $\begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n-1 \\ k \end{pmatrix} + \begin{pmatrix} n \\ k-1 \end{pmatrix}$  to answer the following questions. Assume that $n, m$ are positive integers. Write only the answers without any explanation.

1. What is the value of $F(n, 2)$?

2. What is the value of $F(n, m)$?

3. How many recursive calls are made to the function $F$, including the original call, when evaluating $F(n, m)$.

Comments

People have provided good answer for A and B part. But for C part O(2^n) is upper bound. I am unable to get exact formula for number of calls for particular F(n,m). But following code could be used to get exact answer.
 

public class Test {
    public static int n, m, numberOfRecursiveCalls;
	
	public static int nCm(int a, int b) {
		numberOfRecursiveCalls++;
		if(a<=0||b<=0) return 1;
		else 	return nCm(a-1, b) + nCm(a-1, b-1);		
	}
	public static void main(String[] args) {		
			n = 10;  m = 9;
		    numberOfRecursiveCalls = 0;
			nCm(n,m);
			System.out.println(numberOfRecursiveCalls);	
	}
}

If anyone knows how exact number of calls could be calculated in Pascal's identity. Please mention it in the answer section. It will be great help. 

---

https://stackoverflow.com/questions/26228385/time-complexity-of-recursive-algorithm-for-calculating-binomial-coefficient

---

I didnt seem to still understand how to calculate the Tc for this reccurence, would help if someone elaborated the c part of the question

---

Let Z(n,m) denotes number of function call required then,

Z(n,m) = Z(n-1,m) + Z(n-1,m-1) +2

height of tree = O(n)

number of recursive calls = O(2^n)

Answer 1

$F(n,m)= F(n-1,m)+F(n,m-1)$

Let vertices represent $F(n,m)$ value.

According to rule, we get value of $F(n,m)$ by adding value of vertex left above of it and vertex right above of it.

When counting these, we observe a pattern. Hence to find say $F(4,2)$ we do $F(4,1)+F(3,2)=5+10=15.$

If $C(n,m)$ denotes number of recursive calls for $F(n,m)$ we have,

$C(n,m) = C(n-1,m) + C(n-1,m-1) +2$  

Comments

Thanks for the work!

---

Not able to get the first line in answer,

F(n,m)= F(n-1,m)+F(n,m-1)

but in question it is n-1.

F:F(n-1, m) + F(n-1, m-1);

 

why n is taken here. Please anybody help!

 

---

C(n,m) = C(n-1,m) + C(n-1,m-1) + 2

isn’t this must be 1 instead of 2?

 1 recursive call for C(n,m) itself and rest for c(n-1,m-1) and c(n-1,m)

how extra 1 is coming.??

anyone!!

---

Sorry for the late reply, as ASNR1010 pointed out, The relation is actually $F(n,m) = F(n-1,m)+F(n,m-1)$
refer https://www.geeksforgeeks.org/gate-cs-1997/ question 59.
The question posted here is wrong.

Answer 2

a) $\frac{n(n-1)}{2}$

b) $\frac{n(n-m+1)}{m!}$

Comments

@Anirudh

a) should be

$\frac{(n+1) * (n+2)}{2}$

b) I m struggling for it :p

---

Isn't its simply nCm ??

(a) nC2

(b) nCm = (n * n-1 * n-2  *....* n-m+1 ) / m!

(c) No. Of Recursive Calls = O(2^n)

---

In program it is : 
F:F(n-1, m) + F(n, m-1);

and recurence relation given :

$\begin{pmatrix} n\\ k \end{pmatrix}$  =  $\begin{pmatrix} n-1\\ k \end{pmatrix}$ + $\begin{pmatrix} n-1\\ k-1\end{pmatrix}$

Which one to consider ?

---

@VS. We have to take down one.

Because this program is for calculating nck.

Answer 3

I think this question needs some correction :

1. Recurrence relation is not matching with the function in the algorithm

2.Some base conditions are missing as n>=m.

Due to these mistakes, this question is a little bit ambiguous.

Correct algorithm:

int binomialCoeff(int n, int k)
{
    // Base Cases
    if (k > n)
        return 0;
    if (k == 0 || k == n)
        return 1;
 
    // Recurence
    return binomialCoeff(n-1, k - 1) + binomialCoeff(n - 1, k);
}

Let Z(n,m) denotes number of function call required then,

Z(n,m) = Z(n-1,m) + Z(n-1,m-1) +2    

If you want visualize it it will form a binary tree of maximum height= O(n)

 

So.rougly number of function calls will be O(2^n).

This algorithm can be modified by using dynamic programming which reduces it’s time complexity.

Answer 4

here is what i understood from the question.

hope you all understand :)