Given an integer array of size \(N\), we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The worst-case time complexity of this algorithm is
Answer
(A)
Explanation
The algorithm walks once through the array, comparing each adjacent pair \((a_{i}, a_{i+1})\), and stops as soon as a pair breaks the order. The worst case is an array that really is sorted (or breaks the order only at the very end): all \(N-1\) pairs must then be compared before the algorithm can answer.
So the worst-case time grows linearly with \(N\). It is \(\Theta(N)\), which means it is both \(O(N)\) and \(\Omega(N)\).
B fails because no method can do better: an element that is never examined could break the order, so the time is also \(\Omega(N)\). C and D fail because a single pass is \(O(N)\).
Answer: A