Computer Science Homework: Algorithm Complexity and Recursion

This document provides solutions to a computer science homework assignment focusing on algorithm analysis and design. The solutions cover various aspects of algorithm complexity, including Big O notation and time complexity analysis for different code snippets. Answer 1 analyzes the complexity of a function, demonstrating a quadratic time complexity (O(n^2)). Answer 2 explores the comparison count in an algorithm, concluding with a linear time complexity (O(n)). Answer 3 delves into recursion, predicting the output of a recursive function and providing a code example to verify the result. Finally, Answer 4 discusses the binomial coefficient, presenting both a recursive function and a dynamic programming approach to calculate the coefficient, along with an example calculation. The assignment provides code examples and detailed explanations to help students understand the concepts of algorithm analysis and recursion.

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