Here the elements are in non decreasing order i.e. A[1] ≤ A[2] ≤ …... ≤ A[n] . Create another array B which will store the x - A[i] , where i = 1....n This steps takes O(n) time. Now start traversing the array B from beginning and array A from end untill we find some B[i] == A[j] where i = 1,2,3,...n and j = n,n-1, n-2,....1. This step takes O(n) time. Hence this takes O(n) time . So the answer is option C.
Algorithm
//Create an array B of size n, set flag = false
1. for i =1 to n
2. B[i] = x - A[i]
// loop end here
3. for i = 1 to n && j = n to 1
4. if B[i] == A[j] then
5. flag = true and then break
6. i ++ , j --
//loop end here
7. return flag