0 votes 0 votes Algorithms time-complexity testbook-test-series + – Avik Chowdhury asked Sep 12, 2018 • edited Jul 9, 2022 by Lakshman Bhaiya Avik Chowdhury 682 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply srestha commented Sep 12, 2018 reply Follow Share it will be O(n2) As it is unsorted array If it will be sorted array answer will be O(n) 2 votes 2 votes Magma commented Sep 12, 2018 reply Follow Share yes the answer will be O(n^2) No of subproblems = (No of elements in the sets+1) * (S+1) here In worst case S = n = (n+1)*(n+1) = O(n^2) 0 votes 0 votes Avik Chowdhury commented Sep 12, 2018 reply Follow Share but 0(n^2) is not given here in the option!!! 0 votes 0 votes srestha commented Sep 12, 2018 i edited by Shaik Masthan Sep 12, 2018 reply Follow Share then $c)\theta \left ( n^{2} \right )$ See the loop here will be for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(a[i]+a[j]==x) break; } } 0 votes 0 votes air1ankit commented Sep 12, 2018 reply Follow Share question is not visible, how you guys are solving? 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes answer should be O(nlgn). traverse the every element of the set. For each element a1, the pair would be n = (S - a1 ). Find "n" using Binary Search in O(lgn) time. Thus, total time = n*lgn. Time complexity = O(n*lgn) nephron answered Sep 12, 2018 nephron comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments nephron commented Sep 13, 2018 reply Follow Share sort the array ....still it will take O(nlogn) if the array is sorted, then O(n) is sufficient to find the requirement. how ??? please explain 0 votes 0 votes Shaik Masthan commented Sep 13, 2018 reply Follow Share keep a i at lower index, keep j at last index check the sum pointed by i and j indexes if it is equal, problem solved. if it is more than required, then decrease j if it is less than required, then increase i. stop if i>j 1 votes 1 votes nephron commented Sep 13, 2018 reply Follow Share Yeah right..... now I can recall it was asked in some previous year GATE exam. 0 votes 0 votes Please log in or register to add a comment.