GATE CS 2026 Set 2 Q28 — Asymptotic Worst Case Time and Space Complexity

To find the worst-case time complexity of the fastest algorithm to check the given condition, let us simplify the mathematical statement.

Let $D[k] = A[k+1] - A[k]$ for $k = 1, 2, \ldots, n-1$. The given condition is:

This condition states that for any index $i$ greater than $j$, the difference $D[i]$ must be strictly greater than $D[j]$. This is equivalent to saying that the sequence of differences must be strictly increasing:

Algorithm to Check the Condition:

We can verify this condition by checking if each adjacent pair of differences is strictly increasing:

1. Iterate through the array from $k = 1$ to $n-2$.
2. For each $k$, check if $A[k+2] - A[k+1] > A[k+1] - A[k]$.
3. If the inequality is violated at any point, return False.
4. If the loop completes without any violation, return True.

Complexity Analysis:

• Time Complexity: The algorithm performs a single pass over the array of size $n$, doing a constant number of operations at each step. This takes $\Theta(n)$ time.
• Lower Bound: Any algorithm must examine at least $\Omega(n)$ elements in the worst case. If an algorithm skips even one element, an adversary can alter that element to violate the condition without the algorithm detecting it. Thus, we cannot do better than $\Theta(n)$.

Therefore, the worst-case time complexity of the fastest algorithm is $\Theta(n)$.