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

• A. \(\Theta(n)\)
• B. \(\Theta(\log(n))\)
• C. \(\Theta(n\log(n))\)
• D. \(\Theta(n^2)\)

Hint:

Because strict inequality is transitive, checking only consecutive differences is exactly as strong as checking every pair, so a single linear scan is enough.

Answer 1

The Correct Option is A

Step 1: Translate the condition into plain words.
Look at consecutive gaps in the array, $d_k=A[k+1]-A[k]$. The condition asks that a later gap is always bigger than an earlier gap, for every possible pair of positions. In other words, the gaps themselves must form a strictly increasing sequence. An array with this property is sometimes called strictly convex, since its slope keeps increasing.

Step 2: Realize a full pairwise check is wasteful.
Testing $d_i$ against $d_j$ for every pair with $i$ bigger than $j$ takes roughly $n^2/2$ comparisons. But strict inequality is transitive: once we know each gap is bigger than the one right before it, all along the sequence, every non adjacent pair is automatically true too. So testing neighbours is exactly as strong as testing every pair.

Step 3: Turn this into a single linear scan.
Walk through the array once, keeping a running previous gap value. At each new index compute the current gap and compare it with the previous gap. If it is ever not strictly bigger, the array fails the test right there and the scan can stop early. Otherwise, update the previous gap and move on.

Step 4: Count the operations.
Computing a gap takes constant time, and comparing it to the last gap also takes constant time. Doing this once for each of the $n-1$ gaps costs $\Theta(n)$ overall, with no nested loops and no sorting step.

Step 5: Argue this is already the best possible.
Since the property depends on every element of the array, removing or changing one entry can flip the answer, so any correct checker has to touch every element at least once. That rules out anything faster than linear time, so $\Theta(n)$ is not just achievable, it is optimal.

Step 6: Why the faster and slower options do not fit.
$\Theta(\log n)$ is impossible since the whole array must be read. $\Theta(n\log n)$ suggests some sorting or divide and conquer step, which is not needed once the transitivity shortcut is used. $\Theta(n^2)$ is exactly what the brute force all pairs check would cost, which has already been improved on.

Step 7: Conclude.
$$ \boxed{\Theta(n)} $$
This matches option (A).