0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ OP: It may be helpful to think of this as showing the existence of two possible inputs which should give different answers, but which cannot be distinguished by an algorithm that doesn't read all the input: at least one of the answers such an algorithm gives must be wrong. $\endgroup$ – j_random_hacker Jan 16 '18 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.