edited by
15,612 views
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?

  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 by

6 Answers

Best answer
60 votes
60 votes

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

edited by
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.
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.

AnswerOption A.

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.

Answer:

Related questions