The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+34 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)$
asked in Algorithms by Veteran (59.5k points)
edited by | 1.9k views

2 Answers

+31 votes
Best answer

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

answered by Active (3.3k points)
edited by
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?
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 it.
if the question was to check number of possible values of a and b that give sum <1000

then option D ?
what if the array is not sorted !!! Is the worst case complexity is option D?
if array is like



in this case it takes O(n) time naa
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 ?
If in the question only sorted is given then it means sorted in ascending order
0 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.
answered by (227 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,825 questions
46,802 answers
58,918 users