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 696 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments 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 Shaik Masthan commented Sep 12, 2018 reply Follow Share you are using Binary search ===> it is sorted. if the array is sorted, then O(n) is sufficient to find the requirement. 0 votes 0 votes nephron commented Sep 12, 2018 reply Follow Share where is it mentioned the array is sorted ? Even if the array is sorted how will u find it in O(n) time. I could understand that. Please explain in detail. 0 votes 0 votes Shaik Masthan commented Sep 12, 2018 reply Follow Share if array is not sorted, then how you apply Binary Search? 0 votes 0 votes 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.