59 votes 59 votes Let $S$ be a sorted array of $n$ integers. Let $T(n)$ denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than $1000$ in $S$. Which of the following statement is true? $T (n)$ is $O(1)$ $n \leq T(n) \leq n \log_2 n$ $n \log_2 n ≤ T(n) < \frac{n}{2}$ $T(n) = \left (\frac{n}{2} \right)$ Algorithms gatecse-2000 easy algorithms time-complexity + – Kathleen asked Sep 14, 2014 • edited Jan 24, 2018 by joshi_nitish Kathleen 16.1k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply MrunalJ commented Aug 12, 2021 reply Follow Share What will be the time complexity if the array is not sorted? 0 votes 0 votes Rusty_01 commented Mar 19, 2022 reply Follow Share First, you have to sort the array. Which will take O(nlogn) using any comparison based algo. Then you can use two pointers. The first pointer will point to 0 th element and the second pointer will point to n-1th element. Which will take 0(n). So overall complexity of the program will be 0(nlogn).int find_SumPair( A[], n, K){Sort(A, n); // sort the array (nlogn) // k is the sum which you are looking fori = 0, j = n -1while (i < j) {if(A[i] + A[j] == K) return 1else if(A[i] + A[j] < K)i = i+1elsej = j-1}return -1 } 0 votes 0 votes sayan chowdhury commented Jul 1, 2022 reply Follow Share If the array was unsorted: Array { 8, 4, 5, 2, 1, 3, 7, 0} and sum=3 consider 2 variables m1 and m2 say, initialize m1 and m2 with a[0] and a[1] respectively, if(m1+a[i]<m[2]+a[i]) m2=a[i]; else m1=a[i]; so this takes theta(n) i suppose. 2 votes 2 votes Please log in or register to add a comment.
Best answer 60 votes 60 votes Answer: Option A. Because array is always sorted just check the $1$st two elements. anshu answered Feb 3, 2015 • edited Jun 25, 2018 by Pooja Khatri anshu comment Share Follow See all 16 Comments See all 16 16 Comments reply Show 13 previous comments Aks9639 commented Sep 10, 2019 reply Follow Share the thread is old but it is a quite good question: if array like 1,1000,..... increasing order that would be best case O(1) no of such pair where a +b < 1000 worst case : O(n^2) because array like 0,1,2,3,4,.......1000,....then we have to start from 0 and find other pair upto 1000, and doing the same task for value 1 and 2 and so on then it should be O(n*n)=O(n^2), anyone please tell me if any optimized approach we can use in it for finding the pairs i.e. a+b < 1000. 0 votes 0 votes val_pro20 commented Jan 2, 2021 reply Follow Share @arjun Sir @gatecse if array is unsorted and we have to find two elements with sum greater than 1000 then it will be O(n):::::::::::::::Bubble sort in pass pass will provide largest element in the end and in second pass second largest element . And then test the condition . 0 votes 0 votes raja11sep commented May 20, 2021 reply Follow Share Sorted → Ascending or Descending. if((arr[0]+arr[1])<1000 || (arr[n-1]+arr[n-2])<1000) 2 votes 2 votes Please log in or register to add a comment.
3 votes 3 votes An array is sorted. We need to find only two elements whose sum is less than 1000. So, only first two numbers we need to compare. jay rathod answered Jan 24, 2018 jay rathod comment Share Follow See all 2 Comments See all 2 2 Comments reply anchitjindal07 commented Dec 28, 2018 reply Follow Share @jay rathod But it is not mentioned whether the elements are sorted in ascending order or descending order. What will be the time complexity if array is sorted in descending order. Will it be O(n) or we can do better than that 0 votes 0 votes Kabir5454 commented Mar 28, 2021 reply Follow Share Then we just checked the last two elements☺ 1 votes 1 votes Please log in or register to add a comment.
3 votes 3 votes Sorted → Ascending or Descending. if((arr[0]+arr[1])<1000 || (arr[n-1]+arr[n-2])<1000) print: YES. else print:NO. It’s a constant time operation, with no loop or recursion. Answer: Option A. raja11sep answered May 20, 2021 raja11sep comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes Option A, array is sorted, so just check sum of first two elements. If it would have been greater than 1000 then check sum of last two elements. manikantsharma answered Aug 8, 2019 manikantsharma comment Share Follow See all 0 reply Please log in or register to add a comment.