Database-Management-System
April 18, 2024GATE 2001
April 18, 2024Sorting
|
Question 6
|
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 statements is true?
|
t(n) is O(1)
|
|
|
n ≤ t(n) ≤ n log2 n
|
|
|
n log2 n ≤ t(n) < (n/2)
|
|
|
t(n) = (n/2)
|
Question 6 Explanation:
Since the array is sorted. Now just pick the first two minimum elements and check if their sum is less than 1000 or not. If it is less than 1000 then we found it and if not then it is not possible to get the two elements whose sum is less than 1000. Hence, it takes constant time. So, correct option is (A).
Correct Answer: A
Question 6 Explanation:
Since the array is sorted. Now just pick the first two minimum elements and check if their sum is less than 1000 or not. If it is less than 1000 then we found it and if not then it is not possible to get the two elements whose sum is less than 1000. Hence, it takes constant time. So, correct option is (A).