a lower bound on a problem

Suppose you invent a clever sorting method and it runs in O(n log n) time. A natural question follows: could someone, somehow, ever do better — sort in O(n) time? A lower bound is a promise about the WHOLE problem, not about your particular method: it says that EVERY correct algorithm (within some stated rules) must, in the worst case, do at least this much work. It is a floor under the difficulty itself.

Be careful to separate two very different statements. The running time of one algorithm is an upper bound on the problem: it proves the problem can be solved in at most that much time. A lower bound is the opposite kind of claim and is usually much harder to establish, because you cannot just exhibit one algorithm — you must argue about all possible algorithms at once, including ones nobody has thought of yet. The standard way to make that argument tractable is to fix a model of computation (say, the comparison model) and count the cheapest possible run of the best conceivable algorithm in that model. When the lower bound (the floor) and the upper bound (the best known algorithm) meet, for instance Omega(n log n) and O(n log n) for comparison sorting, we say the problem's complexity is settled, written Theta(n log n).

Two honest cautions. First, a lower bound is always relative to a model: the Omega(n log n) sorting bound holds in the comparison model, yet radix sort beats it by NOT comparing keys — it reads their digits, a different model, so it does not violate the bound. Second, a lower bound on a problem is a worst-case statement: it says some input forces the work, not that every input does. Proving good lower bounds is one of the deepest activities in computer science; for many problems, including everything tied to P versus NP, no strong lower bound is known at all.