The Gateway to Computer Science Excellence
+16 votes

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?

  1. $(n = = 0) || (m = = 1)$
  2. $(n = = 0)$ && $(m = = 1)$
  3. $(n = = 0) || (m = = n)$
  4. $(n = = 0)$ && $(m = = n)$
in Algorithms by
edited by | 2.5k views
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.

mC0 = 1
mC= 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$

2 Answers

+25 votes
Best answer

Answer: C

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

edited by
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.


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.

@vijay where is problem


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


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) ?
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

mCm or mC0

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.

+2 votes

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,484 answers
95,288 users