The GATE Grind

GATE 2026 CS (CS2) – Question 38

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple choice

Consider an array $A$ of integers of size $n$ with indices from 1 to $n$. An algorithm is to be designed to check whether $A$ satisfies
$$\forall i,j \in \{1,\dots,n-1\} \text{ 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?

  1. $\Theta(n)$
  2. $\Theta(\log n)$
  3. $\Theta(n\log n)$
  4. $\Theta(n^2)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $\Theta(n)$

Explanation

The condition requires the consecutive differences $A[2]-A[1], A[3]-A[2], \dots, A[n]-A[n-1]$ to be strictly increasing. These differences can be checked in one left-to-right pass, which takes $\Theta(n)$ time. Also, merely reading the array already takes $\Theta(n)$ time, so no asymptotically faster algorithm is possible. Therefore, option (A) is correct.