Register

What is the time complexity of this problem ?

• edited by
421 views
1 votes
1 votes

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.

• edited by
User Avatar

1 Answer

Best answer
5 votes
5 votes
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
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
2
gshivam63 asked May 21, 2016
471 views
What is the time complexity of this
find(int n) { if(x<2)return; else for(i =1; i<=4; i++) find (n/2); for(i= 1;i< =n*n; i++) sum=sum+1; }
find(int n) { if(x<2)return; else for(i =1; i<=4; i++) find (n/2); for(i= 1;i< =n*n; i++) sum=sum+1; }
User Avatar
2 votes
2 votes
2 answers
3
Amar Vashishth asked Aug 2, 2015
2,446 views
What is the worst case time complexity of this function?
int fun(int n) { int count=0; for (int i= n; i> 0; i/=2) for(int j=0; j< i; j++) count+= 1; return count; }
int fun(int n) { int count=0; for (int i= n; i 0; i/=2) for(int j=0; j< i; j++) count+= 1; return count; }
User Avatar
8 votes
8 votes
2 answers
4
radha gogia asked Jul 19, 2015
20,329 views
Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?
(A) Insertion Sort with time complexity O(kn)(B) Heap Sort with time complexity O(nLogk)(C) Quick Sort with time complexity O(kLogk)(D) Merge Sort with time complexity O(...
User Avatar
Link Copied!