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. i, j ∈ \1, , 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?

GATE CSE 2026 Session 2 Q38: Checking that consecutive differences strictly increase

Algorithms
2 marks
MCQ
−2/3 if wrong

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\} \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?

Try it: multiple choice: exactly one correct option

Wrong answer costs 2/3 mark in GATE.

Show answer and explanation

Answer: A (official GATE 2026 final answer key)

Concept used: The condition says the difference sequence is strictly increasing, which is checked by adjacent comparisons.

First step: Let $d_i = A[i+1] - A[i]$ ; strict increase of $d$ only needs $d_{i+1} > d_i$ for every $i$ (transitivity), and every element must be read.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2026 Session 2 CS question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key

PracticePractise Algorithms questions →Full paperAll GATE CSE 2026 Session 2 questions →

GATE CSE 2026 Session 2 Q38: Checking that consecutive differences strictly increase

Question

Full step-by-step solution

More Algorithms PYQs