Question

3. Let A and B be two sequences of positive integers that are sorted in increasing order. Write an algorithm for determining if there exists an integer a in A and an integer b in B such that x=a+b, for a given positive integer x. Estimate its performance.

Answer 1

Algorithm:

start

Declare sequence A elements in Ascending order

Declare sequence B elements in Ascending order

Input x

for i <- 0, size of A do

for j <- 0, size of B do

if(x==(A[i]+B[j])) do

print x is sum of elements in the sequence of elements A and B

end program

end if

end for

end for

print x is not sum of elements in the sequence of elements A and B

Time complexity Analysis:

start

Declare sequence A elements in Ascending order // Since it runs for 1 time so its Complexity is O(1)

Declare sequence B elements in Ascending order // Since it runs for 1 time so its Complexity is O(1)

Input x // Since it runs for 1 time so its Complexity is O(1)

for i <- 0, size of A do   // Since it runs for n time so its Complexity is O(n)

for j <- 0, size of B do // Since it runs for n time so its Complexity is O(n) and also runs every i loop so overall complexity is O(n²)

if(x==(A[i]+B[j])) do // runs every j loop so its complexity is O(n²)

print x is sum of elements in the sequence of elements A and B   // Since it runs for 0 or 1 time so its Complexity is O(1)

end program

end if

end for

end for

print x is not sum of elements in the sequence of elements A and B

end program

Therefore the overall complexity is O(n²)

Program to verify algorithm:

#include <iostream>

using namespace std;

int main() {

int A[]={1,15,20,23,30,44}; // sequence of elemnts A declaration

int B[]={3,17,26,33,42}; // sequence of elemnts B declaration

int x,sizeA,sizeB; // variable declaration

cout << "Enter an integer: ";

cin>>x; // Accept x value

sizeA=sizeof(A)/sizeof(int); // Find size of sequence A

sizeB=sizeof(B)/sizeof(int); // Find size of sequence B

for(int i=0;i<sizeA;i++) // Loop runs for sequence A

for(int j=0;j<sizeB;j++) // Loop runs for sequence B

if(x==(A[i]+B[j])) // check x is sum of sequence of elements A and B

{

cout<<"x is sum of elements in the sequence of elements A and B"<<endl;

return 0; // Stop program

}

cout<<"x is not sum of elements in the sequence of elements A and B"<<endl;

}

Output:

Q > clang++-7 -pthread -std=c++17 -o main main.cpp ./main Enter an integer: 18 x is sum of elements in the sequence of elements A and B