Worst case will be O(n^2)

Best case O(n)

Best case O(n)

Dark Mode

283 views

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 *?

- $O(1)$
- $O(n^2 \log n)$
- $O(n)$
- $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.

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

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