Question

a) Design in pseudocode an algorithm that gets as input an integer k, and a list of k integers N1, .., Nk, as well as a special value SUM. Your algorithm must locate a pair of values in the list that sum to the value SUM. For example, if your list of values is 3, 8, 13, 2, 17, 18, 10, and the value of SUM is 20, then your algorithm should output "either" the two values 2 and 18, "or" the two values 3 and 17. If your algorithm cannot find any pair of values that sum to the value SUM, then it should print out the message "sorry, there is no such pair of values".

b)   What is the number of comparisons performed by your algorithm in the Best case? In the Worst case?

c)   Express these numbers in the theta (θ) notation.

Answer 1

b) let k=5 ki={10, 2, 3, 15, 10}

Worst case : let SUM=25

then number of comparision is 4+3+2+1;

for k it will be k+(k-1)+(k-2)+......1 = k*(k+1)/2

so worst case is k*(k+1)/2

BestCASE: let sum=12

number of comparisions is 1 (because for first comparision sum =12)

so best case is 1.

#include <bits/stdc++.h>
using namespace std;
void find_pair(int k,int arr[],int SUM)
{
  for (int i = 0; i < k; i++) 
  {
    int tempsum = 0;
    for (int j = i; j < k; j++)
    {
      // Calculate required sum
      tempsum += arr[j];
 
      // Check if sum is equal to
      // required sum
      if (tempsum == SUM)
        {
            cout<<"pairs which sums to given SUM are:"<<arr[i]<<" "<<arr[j]<<endl;
            return ;
        }
    }
  }
  cout<< "sorry, there is no such pair of values";
  return;
}
int main()
{
  int arr[] = {10, 2, 2, 15, 10};
  int k=5;
  int SUM= 25;
  find_pair(k,arr,SUM);
 
}

Note : the code is for referenced and it is written in C++(Since language is not mentioned in problems)