Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Consider the simple problem:
Given a list of objects L of length n, and an object O, determine if O is in L.
It is intuitive that there cannot exist an algorithm a with worst-case time complexity less than O(n) to correctly solve this problem. But without considering individual algorithms, how can one mathematically prove that no faster algorithm exists?
The informal argument is that you need at least $n$ steps to read all the input assuming you can only read at most one element of the input per "step". Of course, you might state that maybe there's an algorithm that doesn't need to read all the input. The argument against that is an adversarial argument which produces an input where such an algorithm will get the wrong answer.
Let $x$ be an input of length $n$ that doesn't contain $O$, and $A$ an algorithm that completes in less than $n$ steps correctly reporting that the input does not contain $O$. There is necessarily an element of the list that $A$ did not look at. Pick one and call that the $i$th element. Running $A$ on $x'$ which is identical to $x$ except that the $i$th element is $O$ then produces the incorrect result. Since $A$ is deterministic and all the inputs $A$ actually reads are the same, then $A$ must behave in the same manner and so it will incorrectly report that the list does not contain $O$.
