in Algorithms edited by
282 views
1 vote
1 vote

Given an array S containing n real numbers, and a real number x. We want to find any two elements p and q in the array such that their sum is greater than the real number x. What is the best possible time complexity to find p and q ?

  1. $O(1)$
  2. $O(n^2 \log n)$
  3. $O(n)$
  4. $O(n \log n)$

Question asks about Best case time complexity . So , if it happens , in the first and second element's sum is greater than x , then it can be done in O(1) time , right ?

Please correct me.

in Algorithms edited by
282 views

1 comment

edited by
Worst case will be O(n^2)

Best case O(n)
0
0

1 Answer

5 votes
5 votes
Best answer
No, in question, best time complexity means best algorithm i.e. what is worst case time complexity of best algorithm.

I think the answer is $O(n)$.

We can find largest and second largest numbers in $S$ in $O(n)$ time. Now see if their sum is greater than $x$, if it is, return these two numbers, otherwise there can't be any pair whose sum is greater than $x$.
selected by

1 comment

thanks bro exactly wat i thought . u refilled my confidence.
0
0

Related questions