282 views

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 ?

### 1 comment

edited
Worst case will be O(n^2)

Best case O(n)

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$.

### 1 comment

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

1 vote
1
3,159 views