Complexity of Binomial Coefficient Calculation

The assignment content discusses various problems related to complexity and recursion. There are four answers provided, each explaining a different concept or problem. Answer 1 explains the complexity of a function that computes the sum of elements from 1 to n, which is O(n^2). Answer 2 analyzes the complexity of another recursive function, concluding that it is also O(n). Answer 3 discusses a recursive function that prints a message a certain number of times and shows how it can be solved using recursion. Finally, Answer 4 explains the concept of binomial coefficients and provides an example of how to calculate C(4,3) using a 2D array.

~~~~~~~~~~~~~~~~~~Answer 1: ~~~~~~~~~~~~~~~~~
 Complexity = O(n^2)
 Function to compute sum is (n/2)^2;
Proof : 1 + 3 + 5 + 7 + 9 + 11 + 2(n-1) = n^2
so : 1 + 3 + 5 + 7 + 9 + n-1 = (n/2)^2;
Some Example :
10 - 25
15 - 49
100 - 2500
1000 – 250000
Prog :
public class Test2 {
public static void main(String[] args) {
System.out.println(func(10000));
}
public static int func(int n) {
int sum = 0;
n = n - ( n % 2 );
for (int k = 1; k < n; k += 2)
for (int j = 0; j < k; ++j)
++sum;
return sum;
}
}
~~~~~~~~~~~~~~~Answer 2: ~~~~~~~~~~~~~~~~~~~~
 No of comparison is same in the all the cases.
 It will be 2(n-1)
 Complexity: O(n).
As Every element is getting compared 2 times except the first
element A[0].
So Complexity is O (2(n-1)) which is equivalent to O (n)
~~~~~~~~~~~~~~~ Answer 3: ~~~~~~~~~~~~~~~~~~~~

 It will be printed 55 Times.
Make the recursion tree to understand more
f(4*4*4*4*4) —
1. f(4*4*4*4*2) — so on
2. f(4*4*4*4*1) — so on
Program to verify
public class Test1 {
private static int count = 0;
public static void main(String[] args) {
System.out.println("Starting....");
fun(4*4*4*4*4);
System.out.println(count);
}
private static void fun(int n) {
if(n<2) {
return;
}
if(n==2) {
count++;
System.out.println("Hii");
}
fun(n/2);
fun(n/4);
}
}
~~~~~~~~~~~~ Answer 4 : ~~~~~~~~~~~~~~~~~~~~~~
Binomail Cofficient:
C(n, k) = C(n-1 , k-1) + C(n-1, k)
C(n,0) = C(n,n) = 1 // Base condition
Recursive Function:
int binomialCoeff(int n, int k)
{
// Base Cases
if (k==0 || k==n)

return 1;
// Recur
return binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}
C(5, 2)
/ \
C(4, 1) C(4, 2)
/ \ / \
C(3, 0) C(3, 1) C(3, 1) C(3, 2)
/ \ / \ / \
C(2, 0) C(2, 1) C(2, 0) C(2, 1) C(2, 1) C(2, 2)
/ \ / \ / \
C(1, 0) C(1, 1) C(1, 0) C(1, 1) C(1, 0) C(1, 1)
It can also be done by making n*n 2 Darray
int binomialCoeff(int n, int k)
{
int C[n+1][k+1];
int i, j;
// Caculate value of Binomial Coefficient in bottom up manner
for (i = 0; i <= n; i++)
{
for (j = 0; j <= min(i, k); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;
// Calculate value using previosly stored values
else
C[i][j] = C[i-1][j-1] + C[i-1][j];
}
}
return C[n][k];
}
Example:
Calculate C(4,3)
N= 4 K = 3
Let's say we want to calculate C(4, 3),
i.e. n=4, k=3:

All elements of array C of size 4 (k+1) are
initialized to ZERO.
i.e. C[0] = C[1] = C[2] = C[3] = C[4] = 0;
Then C[0] is set to 1
For i = 1:
C[1] = C[1] + C[0] = 0 + 1 = 1 ==&gt;&gt; C(1,1) = 1
For i = 2:
C[2] = C[2] + C[1] = 0 + 1 = 1 ==&gt;&gt; C(2,2) = 1
C[1] = C[1] + C[0] = 1 + 1 = 2 ==&gt;&gt; C(2,2) = 2
For i=3:
C[3] = C[3] + C[2] = 0 + 1 = 1 ==&gt;&gt; C(3,3) = 1
C[2] = C[2] + C[1] = 1 + 2 = 3 ==&gt;&gt; C(3,2) = 3
C[1] = C[1] + C[0] = 2 + 1 = 3 ==&gt;&gt; C(3,1) = 3
For i=4:
C[4] = C[4] + C[3] = 0 + 1 = 1 ==&gt;&gt; C(4,4) = 1
C[3] = C[3] + C[2] = 1 + 3 = 4 ==&gt;&gt; C(4,3) = 4
C[2] = C[2] + C[1] = 3 + 3 = 6 ==&gt;&gt; C(4,2) = 6
C[1] = C[1] + C[0] = 3 + 1 = 4 ==&gt;&gt; C(4,1) = 4
C(4,3) = 4 is would be the answer in our example.