0 votes 0 votes l Algorithms sorting time-complexity algorithms gateforum-test-series + – Hardik1997 asked May 26, 2017 retagged Jul 17, 2022 by makhdoom ghaya Hardik1997 809 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Angkit commented May 26, 2017 reply Follow Share Sort the elements, we get O(nlogn).How we can do in O(n)? 0 votes 0 votes akash.dinkar12 commented May 30, 2017 reply Follow Share 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/ 0 votes 0 votes Please log in or register to add a comment.
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/ pawan kumarln answered May 26, 2017 selected Aug 13, 2017 by pawan kumarln pawan kumarln comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Hardik1997 commented May 27, 2017 reply Follow Share Linear search will take O(n) time. Hence the entire process will complete in O(n) time. –1 votes –1 votes pawan kumarln commented May 27, 2017 i edited by pawan kumarln May 27, 2017 reply Follow Share @Hardik1997 how Linear search will take O(n) time......? here in linear search take 1st element and compare to other n-1 element such that (a+b) =x ⇒ (n-1) comparison if not found then take second element and compare to other n-1 element ⇒ (n-2) comparison if not found then take third and so on so total comparison = (n-1) +(n-2) +(n-3)+......1 = O(n2) 0 votes 0 votes ravi kant Gautam commented Apr 23, 2018 reply Follow Share for linear search it will be O(n^2) because we have to use two nested loops. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes I guess O(n log n) is correct option. (Initially sort the array and then apply binary search) kapilbk1996 answered May 29, 2017 kapilbk1996 comment Share Follow See all 2 Comments See all 2 2 Comments reply Arjun commented May 29, 2017 reply Follow Share What will be the binary search criteria? 0 votes 0 votes Saikat commented Jun 29, 2017 reply Follow Share take each element from the array, see if it is bigger than or equal to x. if not then find (x - element) using binary search. Each such search will take O(log n) time. Worst case we have to do this for n-1 elements. So total will take O(nlogn) time. Plus sorting took O(nlogn) time. Total O(nlogn+nlogn) = O(nlogn). 0 votes 0 votes Please log in or register to add a comment.