Let S be a sorted array of n integers. Let T(n) denote the time taken by the…
2000
Let S be a sorted array of n integers. Let T(n) denote the time taken by the most efficient algorithm to determine whether there are two elements in S whose sum is less than 1000. Which of the following statements is true?
- A.
T(n) is O(1)
- B.
n < T(n) < n log₂ n
- C.
n log₂ n < T(n) < C(n, 2)
- D.
T(n) = C(n, 2)
Attempted by 30 students.
Show answer & explanation
Correct answer: A
Since S is sorted in non-decreasing order, the smallest possible sum of any two distinct elements is obtained from the first two elements, S[0] and S[1].
So the most efficient algorithm only needs to check whether S[0] + S[1] < 1000. If this is true, such a pair exists. If it is false, every other pair has sum at least as large, so no valid pair exists.
This requires only two array accesses, one addition, and one comparison, independent of n. Hence T(n) is O(1), so option A is correct.