The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+30 votes
1.3k 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 $0(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 (68.9k points)
edited by | 1.3k views

1 Answer

+25 votes
Best answer

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

answered by Loyal (3.2k 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?
@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
Ohh...sorry..got it.
if the question was to check number of possible values of a and b that give sum <1000

then option D ?


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

32,694 questions
39,293 answers
110,111 comments
36,701 users