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.

The Gateway to Computer Science Excellence

+14 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?

- $(n = = 0) || (m = = 1)$
- $(n = = 0)$ && $(m = = 1)$
- $(n = = 0) || (m = = n)$
- $(n = = 0)$ && $(m = = n)$

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.

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.

+24 votes

+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.

@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

+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

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)!} $

$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

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

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

+4

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

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

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

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 ,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

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.

By the way time complexity with multiple variables is complex.

@Bikram sir please help on this.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,467 answers

195,381 comments

100,318 users