question archive The following algorithm can find all the pairs of values from a given list of k numbers (N1, N2,
The following algorithm can find all the pairs of values from a given list of k numbers (N1, N2,
Subject:Computer SciencePrice:4.86 Bought8
The following algorithm can find all the pairs of values from a given list of k numbers (N1, N2, ..., Nk) with the addition of each pair is equal to SUM. 1. Please fill out each blank below, and make it to be in RED color.
==============Code Begin=====================
Step 1: Get the values for N1, N2, ..., Nk, and SUM
Step 2: Set the value of i to ____
Step 3: Set the value of j to ___
Step 4: Set Flag to be False
Step 5: While (i < k) do steps ____ through ____
Step 6: While ( ___,<= k) do steps 7 through 10
Step 7: If Ni + Nj = _____ then
Step 8: Print (Ni, Nj)
Step 9 Flag = _____
Else
Step 10: Set the value of j to ____
Step 11: Set the value of i to i + 1
Step 12: Set the value of j to _____
Step 13: If Flag == _____ Then
Print the message 'Sorry, there is no such pair of values.'
Else
Print the message 'I am done.'
=============Code End========================
2. Please analyze the time performance for the above algorithm in Big-O notation.
Answer:
Purchase A New Answer
Custom new solution created by our subject matter experts
GET A QUOTE
Answer Preview
Time complexity = O(k2)
while loop is running from i=1 to i<k nested inner while loop is running from j=i+1 to j<=k
Time complexity = O(k2)
first while loop is running from i=1 to i<k and nested inner while loop is running from j=i+1 to j<=k
#include <iostream>
using namespace std;
void printPairs(int N[], int k, int SUM)
{
int i=1;
int j=i+1;
bool flag = false;
while(i < k) // loop of i
{
while(j <= k)
{
if(N[i]+N[j]==SUM)
{
cout<<"("<<N[i]<<","<<N[j]<<")\n";
flag = true;
}
j = j+1; // increment j (N[2] to N[3] for first case)
}
i = i+1; // increment i
j = i+1; // set j again i+1
}
if( flag == false)
cout<<"Sorry, there is no such pair of values.\n";
else
cout<<"I am done.\n";
}
int main()
{
int k;
cout<<"Enter total no.: ";
cin>>k;
int dummy; int N[k+1];
cout<<"Enter the numbers: ";
for(int i=1;i<=k;i++)
cin>>N[i];
int SUM;
cout<<"Enter the value of SUM: ";
cin>> SUM;
printPairs(N,k,SUM);
return 0;
}
Please see the attached file for the complete solution
