Complexity Analysis: a. Write a short Java program that takes an array of int va

Question

Complexity Analysis:
a. Write a short Java program that takes an array of int values as input and find if there is a pair
of numbers with a given sum. What is the total number of operations that occur in terms of
input size n in closed form for worst case scenario. What is the time complexity in Big
O-notation?
Example:
Input: arr[] = {11, 15, 6, 8, 9, 10}, x = 16
Output: 6 + 10 = 16 , true
Input: arr[] = {11, 15, 6, 8, 9, 10}, x = 27
Output: false

b. Write a short Java program that takes an array of int values as input and find if there is a
triplet of numbers with a given sum. What is the total number of operations that occur in
terms of input size n in closed form for worst case scenario. What is the time complexity in
Big O-notation?
Example:
Input: arr[] = {11, 15, 6, 8, 9, 10}, x = 25
Output: 11 + 6 + 8 = 25 , true
Input: arr[] = {11, 15, 6, 8, 9, 10}, x = 39
Output: false
c. Given the following matrix multiplication code. What is the total number of operations that occur in
terms of input size n in closed form. What is the time complexity in Big O-notation? What is the
space complexity of this code?
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
double sum = 0;
for (int k = 0; k < n; k++) {
sum += a[i][k] * b[k][j];
}
c[i][j] = sum;
}
}

Explanation / Answer

complexity is the term related to execution time of algorithm. O notation represent worst case or the case where the output is maximum.

(1)

import java.io.*;
import java.util.*;
public class A
{
public static void main(String args[])
{
int n ;
int a[]=new int[100];
System.out.println("Enter range ");
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
int i , j ;
System.out.println("Enter the elements of array ");
for(i=0;i<n;i++)
{
a[i]=sc.nextInt();
}
System.out.println("Enter the sum to check the condition ");
int sum;
sum = sc.nextInt();
for(i=0;i<n;i++)//loop runs n times
{
  
for(j=0;j<n;j++)//loop runs n times
{
if(i!=j)//constant time execution
{
  
if(a[i]+a[j]==sum)//constant time execution
{
System.out.println(a[i] + " + " + a[j] +" = " +sum);
System.out.println("True ");
System.exit(0);
}
}
}
  
}
  
System.out.println("False ");
}
}   

Output -

aashish@aashish ~/Desktop/My_D/chegg $ java A
Enter range

6
Enter the elements of array

11 15 6 8 9 10
Enter the sum to check the condition

25
15 + 10 = 25
True

So in worst case the algorithm will run with O(n2) complexity as there are two nested for loops

2.

import java.io.*;
import java.util.*;
public class B
{
public static void main(String args[])
{
int n ;
int a[]=new int[100];
System.out.println("Enter range ");
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
int i , j , k ;
System.out.println("Enter the elements of array ");
for(i=0;i<n;i++)
{
a[i]=sc.nextInt();
}
System.out.println("Enter the sum to check the condition ");
int sum;
sum = sc.nextInt();
for(i=0;i<n;i++)//loop runs n times
{
  
for(j=0;j<n;j++)//loop runs n times
{
for(k=0;k<n;k++)//loop runs n times
{
if(i!=j&&j!=k&&k!=i)//constant time execution
{
  
if(a[i]+a[j]+a[k]==sum)//constant time execution
{
System.out.println(a[i] + " + " + a[j] + " + " + a[k] + " = " +sum);
System.out.println("True ");
System.exit(0);
}
}
}
}
  
}

System.out.println("False ");
  
}
}   

output -

aashish@aashish ~/Desktop/My_D/chegg $ gedit B.java
aashish@aashish ~/Desktop/My_D/chegg $ javac B.java
aashish@aashish ~/Desktop/My_D/chegg $ java B
Enter range

6
Enter the elements of array

11 15 6 8 9 10
Enter the sum to check the condition

25
11 + 6 + 8 = 25
True

aashish@aashish ~/Desktop/My_D/chegg $ java B
Enter range

6
Enter the elements of array

3 4 7 8 1 3
Enter the sum to check the condition

65
False

So in worst case the algorithm will run with O(n3) complexity as there are three nested for loops

3.

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
double sum = 0;
for (int k = 0; k < n; k++) {
sum += a[i][k] * b[k][j];
}
c[i][j] = sum;
}
}

time complexity is O(n3) because of 3 nested loops

and space complexity is the space used by algorithm so it's O(1) because we are using sum , that is a single data value .

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.