Computer Sciences > GATE 2026 SET-2 > Algorithms
Consider an array 𝐴 of integers of size 𝑛. The indices of 𝐴 run from 1 to 𝑛. An
algorithm is to be designed to check whether 𝐴 satisfies the condition given below.
∀𝑖,𝑗∈{1,…,𝑛−1} such that 𝑖>𝑗,(𝐴[𝑖+1]−𝐴[𝑖])> (𝐴[𝑗+1]−𝐴[𝑗])
Which one of the following gives the worst case time complexity of the fastest algorithm that can be designed for the problem?
∀𝑖,𝑗∈{1,…,𝑛−1} such that 𝑖>𝑗,(𝐴[𝑖+1]−𝐴[𝑖])> (𝐴[𝑗+1]−𝐴[𝑗])
Which one of the following gives the worst case time complexity of the fastest algorithm that can be designed for the problem?
Correct : a
The correct answer is Option A - Θ(n).
We just need to check if the differences between consecutive elements are strictly increasing.
Compute di = Ai+1 − Ai, and compare each difference with the next one.
Traverse the array once, and for each i, check if:
(Ai+1 − Ai) < (Ai+2 − Ai+1).
If any condition fails, return false. If all checks pass, return true.
This takes one linear scan of the array.
Time Complexity: Θ(n), since we process each element once.
Similar Questions
Match the following
(P) Prim’s algorithm for minimum spanning tree
(i) Backtracking
(Q) Floyd-Warshall algorithm fo...
Consider the following table
Algorithms
Design Paradigms
(P) Kruskal
(i) Divide and Conquer...
Consider functions Function 1 and Function 2 expressed in pseudocode as follows:
Let f1(n) and f2(n) denote the number of times the statement "x = x + 1" is...
Total Unique Visitors
Loading......