An Ω(n) Lower Bound — the Adversary Argument

The algorithm read exactly the same values in both cases, in the same order, so it took the same execution path and produced the same output. But I₁ and I₂ have different correct answers, so at least one of the two outputs is wrong — contradicting correctness.

Hence no correct algorithm can skip an entry on every input, and reading n entries costs Ω(n). Together with the divide-and-conquer solution this places the complexity of the maximum subarray problem between Ω(n) and O(n log n) — and the linear sweep closes the gap: the problem is Θ(n).

Every correct algorithm needs Ω(n) time

Input I₁ — the adversary puts something small in the skipped cell

Input I₂ — the adversary puts something large there instead