Redirected
retagged by
807 views
0 votes
0 votes

l

retagged by

2 Answers

Best answer
1 votes
1 votes

becoz given array is not sorted

1) by using linear search =O(n2)

2) by using binary search=O(n log n)         [O(n log n) for sorting +O(n log n) for binary search ]

3)if we use hash map, This method works in O(n) time if range of numbers is known.

1) Initialize Binary Hash Map M[] = {0, 0, ...}
2) Do following for each element A[i] in A[]
   (a)	If M[x - A[i]] is set then print the pair (A[i], x - A[i])
   (b)	Set M[A[i]]

http://www.geeksforgeeks.org/write-a-c-program-that-given-a-set-a-of-n-numbers-and-another-number-x-determines-whether-or-not-there-exist-two-elements-in-s-whose-sum-is-exactly-x/

selected by
0 votes
0 votes
I guess O(n log n) is correct option. (Initially sort the array and then apply binary search)

Related questions

0 votes
0 votes
0 answers
1
4 votes
4 votes
1 answer
2
Prince Sindhiya asked Aug 23, 2018
1,951 views
. In the standard merge sort algorithm on a list of size n, what is the maximum number of times an item can be compared?a)2b)lognc)n-1d)nlogn
4 votes
4 votes
7 answers
3
pradeepchaudhary asked Jul 9, 2018
12,432 views
Q) Consider a sorted array of n numbers. What would be the time complexity of the best known algorithm to find a pair a and b such that |a-b| = k , k being a positive int...
8 votes
8 votes
2 answers
4