1.6k views

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?

1. $T (n)$ is $O(1)$
2. $n \leq T(n) \leq n \log_2 n$
3. $n \log_2 n ≤ T(n) < \frac{n}{2}$
4. $T(n) = \left (\frac{n}{2} \right)$
edited | 1.6k views

Option A. Because array is always sorted just check the 1st two elements.

edited by
+2
What if array is something like a[]={-100,-50,-25,-18,-10,2,5,9,39,45,90,100,200,550,890,1001} or follows a pattern like this?
+10
@Neelash
then what is problem? the sum of first 2 elements either will be less than 1000 or will be more than 1000. and if first 2 elements(which are smallest one) have sum more than 1000, then no other sum will be less than 1000
0
Ohh...sorry..got it.
0
if the question was to check number of possible values of a and b that give sum <1000

then option D ?
+1
what if the array is not sorted !!! Is the worst case complexity is option D?
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.