Question

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?

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

Hint:

The condition says the difference sequence \(d[k]=A[k+1]-A[k]\) is strictly increasing. This only requires checking consecutive pairs, doable in one linear scan, giving \(\Theta(n)\).

Answer 1

The Correct Option is A

Step 1: Define the difference sequence \(d[k] = A[k+1] - A[k]\) for \(k = 1, \dots, n-1\). The given condition says: for every pair of indices \(i, j \in \{1, \dots, n-1\}\) with \(i > j\), we must have \(d[i] > d[j]\).
Step 2: This condition is exactly the definition of the sequence \(d[1], d[2], \dots, d[n-1]\) being strictly increasing, because 'larger index implies larger value' for every pair is equivalent to \(d[1] < d[2] < \dots < d[n-1]\).
Step 3: By transitivity of the 'less than' relation, checking all \(\binom{n-1}{2}\) pairs is unnecessary. It suffices to verify only the \(n-2\) consecutive comparisons \(d[1] < d[2]\), \(d[2] < d[3]\), ..., \(d[n-2] < d[n-1]\). If every consecutive pair holds, then for any \(i > j\) we get \(d[i] > d[i-1] > \dots > d[j]\) by chaining, so the full condition automatically holds.
Step 4: Computing all \(d[k]\) values takes \(\Theta(n)\) time (one subtraction per index), and checking the \(n-2\) consecutive comparisons takes another \(\Theta(n)\) time. So a single linear pass over the array is sufficient.
Step 5: A lower bound of \(\Omega(n)\) also holds, because any correct algorithm must examine every array element at least once (changing even the last element of \(A\) can flip the answer from 'satisfies' to 'does not satisfy'), so no sub-linear algorithm can be correct in the worst case.
Step 6: Combining the \(O(n)\) upper bound and the \(\Omega(n)\) lower bound, the worst case time complexity of the fastest algorithm is \(\Theta(n)\).
Final Answer: \(\boxed{\Theta(n)}\)