GATE 2026 CS (CS2) – Question 38
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?
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.
More Asymptotic Analysis and Time/Space Complexity questions
- GATE 2025 CS (CS1) Q20
- GATE 2024 CS (CS1) Q17
- GATE 2024 CS (CS1) Q42
- GATE 2024 CS (CS2) Q15
- GATE 2023 CS Q29
- GATE 2023 CS Q54
All Asymptotic Analysis and Time/Space Complexity questions →