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

Additional information

Computational complexity is O($2^{m}$).

Notice answer( expression E) is dependent on conditions (m≥1,n≥0 and m>n). If these conditions are changes then answer(expression E) may change.

---

^mC₀ = 1
^mC_m = 1

Hence, (C) is the correct option!

---

What will be the recurrence relation for this? Anyone please help.

---

@Shubhgupta, Recurrence Relation  is simply $T(m,n) = T(m-1,n)+T(m-1,n-1)$ with base conditions $T(n,n)=1$ , $T(m,0)=1$. It is a Recurrence Relation with $2$ variables.

---

Thanks @ankitgupta.1729 !

---

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

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?