algorithm time complexity madeeasy

Question

Consider the problem that given a set Sof n integers and another integer x, whether or not there exist two elements in S whose sum is exactly x. What is the worst case time complexity for the most efficient algorithm which solves the given problem?

Is not it work like subset sum problem in dynamic programming? Then complexity should be O(n^2).

How O(n logn)?

Comments

@Sajal Mallick I think mistakenly you assumed this problem as subset sum problem, but both are entirely different.

Here we want two elements only, whose sum ==x.

In subset sum problem, we want any subset whose sum ==x and hence we have to consider all 2^n subsets in worst case.

           

Answer 1

Solution:
1. Sort the array → nlogn
2. Consider i=0 and j=n-1(Last element)
3. sum= arr[i] + arr[j]
4. If sum<x then i++ (  we need to increase the value of sum so we should increment i to increase the overall sum as the array is sorted)
5. Similarly if sum>x then j—
6. If sum==x then match found

Therefore total complexity= nlogn + n = nlogn

Additional info:
This problem can be solved in O(n) complexity as well using extra space, this is a famous problem known as “Two Sum”.