Given an integer array of size , 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
both and
but not
but not
neither nor
ANSWER
The worst-case time complexity is both and — option (A).
Official answer: ASource: Official answer key, GATE 2024 CS1 (IISc Bengaluru)
The algorithm makes a single left-to-right pass through the N-element array, comparing each element only with its adjacent neighbor(s).
Such a pass performs at most N-1 comparisons, regardless of the input, giving an unconditional upper bound of O(N) on the running time.
To determine with certainty whether the array is sorted (ascending or descending), the algorithm must inspect every adjacent pair: if any pair were left unchecked, an adversarial input could hide a violation there while every checked pair still looks consistent.
Consider the worst-case inputs for this requirement: an array that actually is fully sorted, or one whose only violation of an otherwise sorted run occurs at the very last adjacent pair. In either case, a single-pass, adjacent-only algorithm cannot safely stop before reaching that last pair.
Hence, in the worst case, the algorithm must perform all N-1 comparisons, giving a lower bound of Omega(N) on the worst-case running time.
A running time that is simultaneously O(N) and Omega(N) is Theta(N) in the worst case.
Therefore the worst-case time complexity is both O(N) and Omega(N), option (A).
KEY IDEA
A single pass over an N-element array that only compares adjacent pairs makes at most N-1 comparisons, so the running time is bounded above by O(N) in every case. In the worst case (e.g. an array that actually is sorted, or one whose only violation is at the very last adjacent pair) the algorithm cannot conclude the answer without inspecting every adjacent pair, so it must also perform Omega(N) work. A bound that is simultaneously O(N) and Omega(N) is Theta(N), so the worst-case complexity satisfies both O(N) and Omega(N).
WATCH OUT FOR
Assuming that because the algorithm might exit early on finding a violation, its worst-case lower bound could be less than Omega(N) — but the worst case includes inputs (e.g. an already-sorted array) where no early exit is possible, forcing all N-1 comparisons, so the lower bound Omega(N) still holds for the worst case.
From the GATE 2024 CS1 paper. Every question of this paper · Download the full paper · All 14 Complexity questions, with notes
