GATE CSE 2026 | Set 2 | Question: 28

Question

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, \ldots, n-1\}$ such that $i>j,(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?

• A. $\Theta(n)$
• B. $\Theta(\log (n))$
• C. $\Theta(n \log (n))$
• D. $\Theta\left(n^{2}\right)$

Answer 1

The correct answer is Option 1: $\Theta(n)$.

The Simple Logic

The mathematical condition simply means that the difference (or "gap") between adjacent numbers must strictly increase as you move from left to right through the array.

Quick Example

Let's check the array [10, 12, 15, 19, 24]:

• Gap 1: 2 (12 - 10)

• Gap 2: 3 (15 - 12)

• Gap 3: 4 (19 - 15)

• Gap 4: 5 (24 - 19)

Because the gaps (2, 3, 4, 5) keep getting bigger, the array satisfies the condition!

Why $\Theta(n)$?

To verify this, you do not need nested loops. You only need to loop through the array exactly once to check if the current gap is bigger than the previous one. Since it only takes one single pass, the time complexity is linear: $\Theta(n)$.

Answer 2

This Simply can be done without Pen and Paper. Just Read this carefully.

\[
a = (A[i+1] - A[i])
\]
is simply the "gap'' between two numbers next to each other.

\[
b = (A[y+1] - A[y])
\]
is simply the ``gap'' between two numbers next to each other.

Now,
\[
\forall i > j,\ \text{Gap}_i > \text{Gap}_j.
\]

\[
\Rightarrow\ a > b
\]

This means a line of people is arranged strictly by height

\[
\Rightarrow\ \text{One single pass through an array.}
\]

\[
\Rightarrow\ \Theta(n)
\]

 

Answer 3

It is one of the tricky question i think!!

Answer 4

The problem asks for the fastest algorithm to check the following condition for an array $A$ of size $n$:

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

Analysis of the Condition

The condition essentially states that the difference between adjacent elements must be strictly increasing as we move through the array.

• Let $D[i] = A[i+1] - A[i]$ for $i = 1, \dots, n-1$.

• The condition simplifies to: $D[n-1] > D[n-2] > \dots > D[1]$.

Complexity Determination

To verify this condition, an algorithm must check if every adjacent difference is larger than the previous one:

1. Calculate $D[1] = A[2] - A[1]$.

2. Calculate $D[2] = A[3] - A[2]$ and check if $D[2] > D[1]$.

3. Continue this for all $n-1$ differences.

Since you must examine every element of the array at least once to ensure the condition holds globally, the algorithm requires linear time. There is no way to skip elements (like in a binary search) because a single "dip" in the difference magnitude anywhere in the array would invalidate the condition.

• Fastest Algorithm: A single pass through the array.

• Worst-case Time Complexity: $\Theta(n)$.

Correct Option: A. $\Theta(n)$

Answer 5

We can solve this problem in linear time by examining the differences between consecutive elements.

First, create a difference array D, where:

D[i] = A[i+1] - A[i]

This requires one traversal of the array.

Next, check whether the difference array D is strictly increasing. In other words, verify that:

D[i] > D[i-1]

for every valid index i.

This requires a second traversal.

If all consecutive differences are strictly increasing, then the given condition is satisfied. Otherwise, the condition is not satisfied.

Complexity Analysis

• Time Complexity: O(n)

• One traversal to compute the difference array.

• One traversal to verify that the differences are strictly increasing.

• Space Complexity: O(n)

• If the difference array is stored explicitly.

The space complexity can be optimized to O(1) by computing and comparing consecutive differences on the fly, eliminating the need for a separate difference array.

Answer 6

Carefully read the question first.

The condition they provided 

 i>j,(A[i+1]−A[i])>(A[j+1]−A[j])

this simply means the sequence of differences D must be strictly increasing.

you might get confused because of the use of i,j here even i got confused there but the catch is we dont need to compare each differences.We just have to check the neighbours .

Analogy- Think of it like checking if a line of people is sorted by height. You don,t need to compare person at position 1 to positon 9 or person at 2 to person 7. You can simply compare the current and next person and achieve the sorted line height wise.

so here also checking consecutive pair of differences is enough.

Algorithm: 

Walk through the array once computing each consecutive differences.

check if each difference is bigger than the previous one.

if yes throughout condition holds,if no somewhere then the condition fails that's it.

This is just one pass through the array, so it takes O(n) time. You cannot do it faster than this because you have to check every element atleast once to be sure.