Question

Question 3:

You are requested to design an algorithm to check whether a key pair (sum of two numbers only) exist in a given array (of size N) or not. If the key pair exists at least once then the algorithm should return “True”; otherwise “False”.

For example, given an array A[8, -3, 9, 5, -3, 11, 2, -7, 4, 11] where the key pair is 13, then the required algorithm should return “True” because such pair exist at least once ex:(9+4). Another example, given the same array, where the key pair is 21, the required algorithm should return “false”, as there is no any pair with sum equal to 21

1. Another algorithm would first sort the array to take advantage of the sorted value to facilitate the search for the required key pair :  
   1. Design this algorithm [Hint: don't design a sorting function, simply use Sort(A) to do the job of sorting without going into the sorting details].
   2. In order to get a better performance, which sorting algorithm “Sort(A)” would you choose to do this task?

iii. What is the complexity of this algorithm in the best and worst case? (5 marks

Answer 1

Find the solution to the above question below, do read all the steps provided carefully and in case of any comments do comment below. If found helpful please upvote this.

Algorithm

1. First sort the given array in ascendigng order
2. now we will use two pointer algorithm that is take two indexes. first will point to 0 (start of array) and other at n-1(end of array), let them be a and b
3. check if arr[a]+arr[b] == given sum , if yes then return true ,
4. else check if the obtained sum is less than the given if yes then increment a by 1
5. if the obtained sum was more than the given sum then decrement b by 1
6. repeat the steps until a < b
7. that's all if we don't find anything and reach the end of lopp then return False.

Code

A = [8, -3, 9, 5, -3, 11, 2, -7, 4, 11]

Sort(A)

a = 0

b = n-1

sum = 19

while a < b:

    if A[a]+A[b] == sum:

        return True

    if A[a]+A[b] < sum:

        a = a+1

    else:

        b = b-1

return False

Screenshot of code

Part ii

In order to get a better performance merge sort should be used, merge sort has worst case time complexity of O(nlog(n)) which is better than any other sorting algorithm

Part iii

Sorting will take nlog(n) time in any case

Now for best case finding the pair will take O(1) so overall it will be O(nlog(n))

In worst case findign teh pair will take O(n/2) so overall it will O(nlog(n)) + O(n/2) which is same as O(nlog(n))