GATE CS 2024 Set 1 Q7 — Asymptotic Worst Case Time and Space Complexity

To determine if an array of size $N$ is sorted in either ascending or descending order, any algorithm must verify the relationship between all adjacent elements in the worst case.

Worst-Case Analysis:

• The worst-case scenario occurs when the array is indeed fully sorted (either ascending or descending), or when the sorting order is violated only at the very last pair of elements.
• In such cases, the algorithm must scan the entire array and perform comparisons for all adjacent pairs.
• For an array of size $N$, there are exactly $N - 1$ adjacent pairs: $(A[0], A[1]), (A[1], A[2]), \dots, (A[N-2], A[N-1])$.
• Thus, the algorithm performs exactly $N - 1$ comparisons in the worst case.

Since the number of operations in the worst case is proportional to $N$, the worst-case time complexity $T(N)$ is $\Theta(N)$.

By the definitions of asymptotic notations:

Therefore, the worst-case time complexity is both $\mathrm{O}(N)$ and $\Omega(N)$.