Usually in AlgorithmAnalysis we are looking for upper bounds on cost, as in "Algorithm X solves problem Y in no more than O(n22/7) time in the worst case." Upper bounds are useful when we want to advertise that our algorithm is good. But what if we want to argue that no other algorithm can be better, or perhaps that some problem is so hard that we can't possibly hope to find a good solution to it?
For this we need a lower bound. Lower bounds come in two flavors:
A lower bound on an algorithm is just a big-Omega bound on its worst-case running time. "I don't know exactly how long Bogosort takes in general, but I can prove its worst-case time is Ω(n2)."
A lower bound on a problem is a big-Omega bound on the worst-case running time of any algorithm that solves the problem:
"Any comparison-based sorting routine takes Ω(n log n) time." (True; see ComparisonBasedSortingLowerBound.)
"There is an ε > 0 such that any algorithm for IndependentSet takes Ω((1+ε)n) time." (Might be true. Fame and fortune await anyone who can prove it. See PvsNp.)
1. Information-theoretic lower bounds
Most algorithms have to read all of their input to produce the correct output: this takes Ω(n) time.
If there are m possible outputs for inputs of size n and each step yields O(1) bits of information, then we need to take Ω(m) steps. This is the basis of the ComparisonBasedSortingLowerBound.
In general, if we can show that executions that take less than T time can't distinguish between inputs A and B for which f(A) ≠ f(B), then T is a lower bound on correct implementations.
2. Lower bounds by reduction
Suppose we already have a lower bound S(n) on some problem A, and that there is a reduction from A to some other problem B. Formally, a reduction is a function f such that A(x) = B(f(x)). Let Tf(n) be an upper bound on the time to compute f(x) when |x| = n, and let TB(n) be an upper bound on the time to compute B(x) when |x| = n. Then computing A(x) as B(f(x)) with |x| = n takes time at most Tf(n) + TB(Tf(n)). (The odd second term comes from the fact that Tf(n) is an upper bound on the length of the output of f(x); note that we are also assuming here that TB is nondecreasing.)
An important special case of this is when Tf = O(nc) and TB = O(nd) for some c and d. Then Tf(n) + Tf(TB(n)) = O(nc) + O(ncd) = O(ncd). In words:
- Any problem that has a polynomial-time reduction to a polynomial time problem can be solved in polynomial time.
How do we get lower bounds out of this? Since S(n) ≤ Tf(n) + Tf(TB(n)), we have TB(n) ≥ Tf-1(S(n) - Tf(n)). For example:
Suppose there is a reduction f from sorting to some problem B that takes O(n) time and does not examine the elements of the sorting problem. Then B(f(x)) is a comparison-based sorting algorithm if B uses only comparisions, and TB(n) = Ω(n log n) - O(n) = Ω(n log n).
Suppose there is no polynomial-time algorithm for A but there is a polynomial-time reduction from A to B. Then there is no polynomial-time algorithm for B. This is the central idea behind NP-completeness, discussed in PvsNp.
3. Can we prove interesting lower bounds?
Lower bounds on problems are the really interesting results, since those are the ones that say that the problem is too hard instead of saying that we are too dumb to come up with a better algorithm. But we aren't very good at proving them; in fact, the comparison-based sorting lower bound is about the only non-trivial lower bound we've got for a traditional algorithmic problem. The difficulty is that it is very hard to write a lower bound proof that covers all possible algorithms, including the ones no one has thought of yet---algorithms are slippery and clever, and there are a lot of them.
So instead we fall back to classifying problems by how hard they appear to be relative to other problems. This classification task is the core of ComputationalComplexityTheory. For many such classes of problems we cannot prove that all the problems in some class are hard, but we can prove that each is hard if and only if all the others are (for an appropriate definition of "hard"). This is not quite as good as a real lower bound, but appears to be the best we can do so far.