GATE CS 2024 Set 1 — Question 17

To determine if an array of size $N$ is sorted (either ascending or descending), an algorithm must examine every element at least once to ensure no pair violates the sorting order. A single-pass algorithm that compares each element with its adjacent neighbor will perform exactly $N-1$ comparisons in the worst case (e.g., when the array is indeed sorted or the violation occurs at the very end). Since the number of operations is proportional to $N$, the time complexity is $T(N) = \Theta(N)$. By the definitions of asymptotic notation, $f(n) = \Theta(g(n))$ implies that $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$. Therefore, the worst-case time complexity is both O(N) and $\Omega(N)$.