The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+34 votes
2.1k 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 $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.6k points)
edited by | 2.1k 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
+3
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?
+12
@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
0
Ohh...sorry..got it.
0
if the question was to check number of possible values of a and b that give sum <1000

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

[1,1000,1002,1045,1100,1500]

??

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

In that case, check sum of last two elements.
0

@Yashaswini Vanaja

Why O(n)?

It will take O(1) only.

0
If question is a+b=1000 then what is the time complexity????
0
O(n)
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)
Answer:

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

42,516 questions
48,528 answers
155,031 comments
63,377 users