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.4k points)
edited by | 1.6k views

2 Answers

+29 votes
Best answer

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

answered by Active (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
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?
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 (101 points)

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

34,770 questions
41,730 answers
41,381 users