GATE CS 2000 Q1.15 — Asymptotic Worst Case Time and Space Complexity

Since the array $S$ of $n$ integers is already sorted in non-decreasing order, we have:

To determine if there exist any two elements in $S$ whose sum is less than $1000$, we only need to look at the two smallest elements in the array, which are $S[0]$ and $S[1]$:

1. Case 1 ($n < 2$): It is impossible to find two elements, so the answer is immediately false. This takes $O(1)$ time.
2. Case 2 ($n \ge 2$): The minimum possible sum of any two distinct elements in $S$ is $S[0] + S[1]$.
   • If $S[0] + S[1] < 1000$, then we have found two elements whose sum is less than $1000$.
   • If $S[0] + S[1] \ge 1000$, then for any other pair of indices $i \neq j$, we have $S[i] + S[j] \ge S[0] + S[1] \ge 1000$. Thus, no such pair can exist.

Therefore, the problem reduces to checking if $S[0] + S[1] < 1000$. Since array indexing, addition, and comparison are basic operations that take constant time, the most efficient algorithm runs in $O(1)$ time.

Thus, $T(n)$ is $O(1)$.