2.4k 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 | 2.4k views

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

edited
+3
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?
+13
@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?
0
if array is like

[1,1000,1002,1045,1100,1500]

??

in this case it takes O(n) time naa
0
What if the array is sorted in descending order and sum of first two integers is greater than 1000?

Ex: 2000,1500,1000,.............,500,100,50 ?
0
If in the question only sorted is given then it means sorted in ascending order
0
@divakar17

In that case, check sum of last two elements.
0

Why O(n)?

It will take O(1) only.

0
If question is a+b=1000 then what is the time complexity????
0
O(n)
0

@anshu 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

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.
0

@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

1
2