The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+30 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 $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?
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 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
36,701 users