The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
1.9k views

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 Boss (16.3k points)
edited by | 1.9k views
0
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.
+4

mC0 = 1
mC= 1

Hence, (C) is the correct option!

0
What will be the recurrence relation for this? Anyone please help.
+1
@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.
+1

Thanks @ankitgupta.1729 !

2 Answers

+23 votes
Best answer

Answer: C

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

by Boss (33.8k points)
edited by
+2
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.
+4

@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

+4
@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
+4
@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)!} $
0
and @vijay  i did not get u why u r showing that one
+3
It is the proof of the question.
0
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??
+3
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
0
Can anyone confirm time complexity ?

O(2^m) ?
+2
@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)
+1
@Ahwan ur recurrence relation is fine but you cannot say that n is a constant
0
@VS I guess you cant find the recurrence relation otherwise..  if n is not a constant.
+1
@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
+1
@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.
0

It's base case need to be taken care.

Return 1 when you reach base case

which is

mCm or mC0

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

@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
ans..(C).
by Active (5k points)
Answer:

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
49,807 questions
54,713 answers
189,262 comments
79,704 users