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: Understand what the condition really says.
Define the difference sequence
\[ d_k = A[k+1]-A[k] \quad \text{for } k=1,\ldots,n-1 \]
The condition says that for every pair \(i>j\),
\[ d_i>d_j \]
This means the differences must be in strictly increasing order as \(k\) goes from \(1\) to \(n-1\):
\[ d_1<d_2<\cdots<d_{n-1} \]

Step 2: Show that checking only consecutive differences is enough.
Suppose \(d_1<d_2<\cdots<d_{n-1}\) holds for every consecutive pair. Then for any \(i>j\), we can chain the inequalities
\[ d_j<d_{j+1}<\cdots<d_i \]
and by transitivity of the strict less than relation, \(d_j<d_i\), which is exactly the required condition for that pair. So we never need to check all \(\binom{n-1}{2}\) pairs directly, checking the \(n-2\) consecutive pairs is enough.

Step 3: Design the algorithm.
First, compute the \(n-1\) differences \(d_1,\ldots,d_{n-1}\) by scanning array \(A\) once. This takes
\[ \Theta(n) \]
Second, scan through \(d_1,\ldots,d_{n-1}\) once and check that each value is strictly less than the next one. This also takes
\[ \Theta(n) \]
As soon as any \(d_k \geq d_{k+1}\) is found, the algorithm can stop and report that \(A\) fails the condition.

Step 4: Add up the total time.
\[ \Theta(n)+\Theta(n)=\Theta(n) \]

Step 5: Explain why the algorithm cannot be faster than \(\Theta(n)\).
Any correct algorithm must look at every element of \(A\) at least once, because changing even a single unread element could change whether the condition holds. So no algorithm can do better than linear time, and \(\Theta(n)\) is both achievable and optimal.

Step 6: Rule out the other options.

(B) \(\Theta(\log(n))\): Too fast, since the whole array must be examined at least once. Incorrect.

(C) \(\Theta(n\log(n))\): This would be needed if the array had to be sorted or searched with comparisons across all elements, but the transitivity trick removes that need. Incorrect, since it is more than what is required.

(D) \(\Theta(n^2)\): This is what a naive algorithm would take if it checked every pair \(i>j\) directly instead of using transitivity. It works but is not the fastest possible. Incorrect.

Step 7: Final conclusion.
\[ \boxed{\Theta(n)} \]
Hence, the correct option is (A).