Question

Algorithm problem

2 [2.3-7] Describe a Θ(nlgn) algorithm that, given a set S of n integers and another integer ,determines whether or not there exist two elements in S whose sum is exactly x.

Answer 1

Algorithm: //to find whether in a given set S of n integers and another integer x, there exist two elements in S whose sum is exactly x.
INPUTS:
A[]//ARRAY
X //sum
STEP 1) Sort the array in increasing order.//use mergesort or heapsort which runs in theta(nlogn)
STEP 2) declare two variables :l,r
(a) Initialize variable l to the leftmost index: l = 0
(b) Initialize variable r the rightmost index: r = array_size-1
STEP 3) Loop while l < r //run until l<r
(a) If (A[l] + A[r] == x) then return TRUE//means found
(b) Else if( A[l] + A[r] < x ) then l++
(c) Else r--
STEP 4) No candidates in whole array - return FALSE//MEANS NOT FOUND
total complexity : nlogn+n = theta(nlogn)