GATE CS 2026 Set 2 Q.38: Searching and Sorting Algorithms

Consider an array $A$ of integers of size $n$ . The indices of $A$ run from $1$ to $n$ . An algorithm is to be designed to check whether $A$ satisfies the condition given below.

\forall i, j \in \{1, \dots, n - 1\} \text{ such that } i > j, \quad (A[i + 1] - A[i]) > (A[j + 1] - A[j])

Which one of the following gives the worst case time complexity of the fastest algorithm that can be designed for the problem?

$\Theta(n)$

$\Theta(\log(n))$

$\Theta(n \log(n))$

$\Theta(n^2)$

Official answer and solution

Official answer: A
From: Official GATE 2026 answer key

Solution

Observe that the condition simply states that the adjacent difference sequence $D[k] = A[k+1] - A[k]$ is strictly increasing.

Let $D[k] = A[k+1] - A[k]$ for $k = 1, \dots, n-1$ . By transitivity of $>$ , the condition $D[i] > D[j]$ for all $i > j$ holds if and only if $D[k+1] > D[k]$ for every consecutive index $k \in \{1, \dots, n-2\}$ . We can verify this in a single pass over the array in $\Theta(n)$ time, and in the worst case every element of $A$ must be inspected at least once ( $\Omega(n)$ ). Therefore, the optimal worst-case time complexity is $\Theta(n)$ .

Final answer

Option (A)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 2 (CS2)
Question: 38 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source