GATE 2026 CS2 Q.38: solution and answer

Official answer: ASource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

1. Let $d[k]=A[k+1]-A[k]$ for $k=1,\dots ,n-1$ — the sequence of consecutive differences of $A$.

2. The given condition says: for every pair $i>j$ in $\{1,\dots ,n-1\}$, $d[i]>d[j]$. This is exactly the statement that $d[1]<d[2]<\cdots <d[n-1]$, i.e. $d$ is strictly increasing.

3. Strict inequality ($<$) is transitive, so it suffices to check only the $n-2$ consecutive pairs $d[1]<d[2],d[2]<d[3],\dots ,d[n-2]<d[n-1]$: if every adjacent pair satisfies $<$, then by transitivity every non-adjacent pair with $i>j$ also satisfies $d[i]>d[j]$.

4. Algorithm (upper bound): scan the array once left to right, computing each $A[k+1]-A[k]$ in $O(1)$ time and comparing it with the previous difference. This does $O(n)$ arithmetic operations and $O(n)$ comparisons in total, so the condition can be checked in $O(n)$ time.

5. Lower bound: whether $A$ satisfies the condition depends on every entry of $A$ — changing any single unread entry can change some $d[k]$ and flip the answer. So any correct algorithm must inspect all $n$ entries in the worst case, giving $\Omega (n)$.

6. Since $O(n)$ (achievable) meets $\Omega (n)$ (necessary), the worst-case time complexity of the fastest possible algorithm is $\Theta (n)$ — option (A).