The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
421 views

Consider the following function.

Function F(n, m:integer):integer;
begin
    If (n<=0 or (m<=0) then F:=1
    else
      F:F(n-1, m) + F(n, m-1);
    end;

Use the recurrence relation  $\begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n-1 \\ k \end{pmatrix} + \begin{pmatrix} n-1 \\ k-1 \end{pmatrix}$  to answer the following questions. Assume that $n, m$ are positive integers. Write only the answers without any explanation.

  1. What is the value of $F(n, 2)$?

  2. What is the value of $F(n, m)$?

  3. How many recursive calls are made to the function $F$, including the original call, when evaluating $F(n, m)$.

asked in Algorithms by Veteran (59.6k points) | 421 views
0

Hi,

I think question needs small correction. 

F:F(n-1, m) + F(n-1, m-1);
0

People have provided good answer for A and B part. But for C part O(2^n) is upper bound. I am unable to get exact formula for number of calls for particular F(n,m). But following code could be used to get exact answer.
 

public class Test {
    public static int n, m, numberOfRecursiveCalls;
	
	public static int nCm(int a, int b) {
		numberOfRecursiveCalls++;
		if(a<=0||b<=0) return 1;
		else 	return nCm(a-1, b) + nCm(a-1, b-1);		
	}
	public static void main(String[] args) {		
			n = 10;  m = 9;
		    numberOfRecursiveCalls = 0;
			nCm(n,m);
			System.out.println(numberOfRecursiveCalls);	
	}
}

If anyone knows how exact number of calls could be calculated in Pascal's identity. Please mention it in the answer section. It will be great help. 

2 Answers

+1 vote
a) $\frac{n(n-1)}{2}$

b) $\frac{n(n-m+1)}{m!}$
answered by Veteran (61.2k points)
+1
@Anirudh

a) should be

$\frac{(n+1) * (n+2)}{2}$

b) I m struggling for it :p
0
Isn't its simply nCm ??

(a) nC2

(b) nCm = (n * n-1 * n-2  *....* n-m+1 ) / m!

(c) No. Of Recursive Calls = O(2^n)
+1
In program it is : 
F:F(n-1, m) + F(n, m-1);

and recurence relation given :

$\begin{pmatrix} n\\ k \end{pmatrix}$  =  $\begin{pmatrix} n-1\\ k \end{pmatrix}$ + $\begin{pmatrix} n-1\\ k-1\end{pmatrix}$

Which one to consider ?

0 votes
a) $(n+1)(n+2)\over2 $

b) $(n+m)!\over n!m!$

c) $2{{(n+m)!}\over{n!m!}} - 1$
answered by (139 points)

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

42,686 questions
48,650 answers
156,455 comments
63,961 users