GATE IT 2006 | Question: 52

Question

The following function computes the value of  $\binom{m}{n}$ correctly for all legal values $m$ and $n$ ($m ≥1, n ≥ 0$ and $m > n$)

int func(int m, int n)
{
    if (E) return 1;
    else return(func(m -1, n) + func(m - 1, n - 1));
}

In the above function, which of the following is the correct expression for E?

• A. $(n = = 0) || (m = = 1)$
• B. $(n = = 0)$ && $(m = = 1)$
• C. $(n = = 0) || (m = = n)$
• D. $(n = = 0)$ && $(m = = n)$

Comments

Why not option (d)  is the answer?????

---

$ \textbf{m > n}$

Why we are not considering this condition. Due to it we should not take $m == n$

---

@KARAN

because those are the conditions to the input of the functions and they can change inside the function like in this case due to recursion.

 

Answer 1

Answer: C

Because $\binom{m}{0}$ = $1$ and $\binom{n}{n}$ = $1$.

Comments

I got its ans by substituting some values, but not able to understand how this recursion is giving C(m,n).
@Arjun sir , please spread some light on it.

---

@vijaycs

We know by drawing pascals triangle we can find C(m,n).

And given recursion leads to pascal triangle.

I think following link may address ur concern.

https://en.wikipedia.org/wiki/Binomial_coefficient#Recursive_formula

https://en.wikipedia.org/wiki/Pascal%27s_triangle

---

@vijay where is problem

Say

we are finding value $_{2}^{4}\textrm{C}$=$_{2}^{3}\textrm{C}$+$_{1}^{3}\textrm{C}$

@Rajesh it is just finding combination

---

@Srestha, I did not get you . . .

$nC_{r} = (n-1)C_{r} + (n-1)C_{r-1}\\
          = \frac{(n-1)!}{r!(n-1-r)!} + \frac{(n-1)!}{(r-1)!(n-r)!}\\
          = \frac{(n-1)!}{(r-1)!(n-1-r)!}.[\frac{1}{r} - \frac{1}{(n-r)}]\\
          = \frac{(n-1)!}{(r-1)!(n-1-r)!}.\frac{n}{r(n-r)}\\
          =\frac{(n)!}{(r)!(n-r)!} $

---

and @vijay  i did not get u why u r showing that one

---

It is the proof of the question.

---

why option A is incorrect.

let func(2,1)   // m=2, n=1

func(2,1) = func(1,1)  + func(1,0)

in this case option A & option C both gives correct ans.

Can anyone give a counter example for option A??

---

Option (a) is incorrect.

According to option (a) :: func(m,n)=1 if n==0 or m==1

Now,

f(3,3)=f(2,3) + f(2,2)

f(2,3)= f(1,3) + f(1,2) = 1+1=2 //here m=1

f(2,2)=f(1,2)+f(1,1)= 1+1 = 2

So, f(3,3)=4 ...This is wrong

as f(3,3)=1 and not 4.Hence option (c) correct

---

Can anyone confirm time complexity ?

O(2^m) ?

---

@VS
From m & n, m is a variable & n should be a constant.
I guess T(m) =2T(m-1)+c
so seems as O(2^m)

---

@Ahwan ur recurrence relation is fine but you cannot say that n is a constant

---

@VS I guess you cant find the recurrence relation otherwise..  if n is not a constant.

---

@Ahwan ,but how can you say that n is a constant ? We are computing mCn.

And regarding the recurrence relation.

See if we try to make a Recurrence tree for it. We will surely m-levels but it will not be a complete BT because of some gaps caused by n.

But if we try to appoximate ..Recurrence relation would be that only and TC=2^m

---

@VS  yes if  n is a variable then the recurrence relation I have given is not correct.
By the way time complexity with multiple variables is complex.

@Bikram sir please help on this.

---

It's base case need to be taken care.

Return 1 when you reach base case

which is

^mC_m or ^mC₀

---

why not D? && means we have to check for both conditions to be true isnt?

---

@Pranav Because if(E) means if(E!=0); so if any one of them is FALSE then we come out of the loop.

---

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

This is the recursive definition of Combinations of m objects chosen n at a time.

We all know, when does this function returns 1, it is only when nCn or nC0

---

@ vijaycs

In the third line it must be

[1/r  + 1/(n-r)]

you mistyped – in case of +.

---

@Ahwan sir!

This code is somewhat similar to the 01KS problem so i think the time complexity given by you must be correct. 

Answer 2

$\binom{m}{0} or   (m==n) \binom{m}{n}$

return 1;

(n==0) || (m==n)

Amswer : C

Comments

That's what is my doubt. N==0 is true and m==n is true , so whole statement is true right. So opt d also serves the solution.

---

Ok, value of $\binom{6}{6}$ is 1.

so here n is 6, according to d option (n==0) && (m==n), (n==0) is also should be true then whole statement return 1, but here it will not return 1.

while taking to option c. (n==0)||(m==n) the whole statment return 1.

same you also check with $\binom{6}{0}$

---

Missed a fine logic,now I get that. Thanks a lot.

Answer 3

If we put m=1, then we can put only one value of n i.e. 0 and putting n=0, we will get the answer as 1. Then why option (a) is not correct?