Lower-Bound Arguments

Lower-Bound Arguments

Lower bounds are estimates on a minimum amount of work needed to solve a problem. To find the efficiency of an algorithm with respect to other algorithms for the same problem, it is desirable to know the best possible lower bound. Knowing such a lower bound can tell  how much improvement had to achieve in our quest for a better algorithm for the problem.

Lower bounds may be exact counts or efficiency classes (big Ω). A lower bound is tight if there exists an algorithm with the same efficiency as the lower bound. 

There are a number of methods that can be used to establish lower bounds:

• trivial lower bounds 

• information-theoretic arguments (decision trees) 

• adversary arguments 

• problem reduction 

Trivial Lower Bounds

The simplest method of obtaining a lower-bound class is based on counting the number of items in the problem’s input that must be processed and the number of output items that need to be produced such a count yields a trivial lower bound. Trivial lower bounds are often too low to be useful.

Trivial lower bounds are based on counting the number of items that must be processed in input and generated as output to solve a problem

Information-Theoretic Arguments

The information-theoretical approach seeks to establish a lower bound based on the amount of information it has to produce. The lower bound is based on the number of bits of information needed to uniquely specify the answer or some other structure related to the problem. 

Information-theoretic lower bounds proved to be quite useful for many problems involving comparisons, including sorting and searching.

Adversary Arguments

Another approach to finding lower bounds is the adversary argument. This method depends on a

“adversary” that makes the algorithm work the hardest by adjusting the input. The solution produced by the adversary must be consistent with what the algorithm already knows or calculated. 

Problem Reduction

The complexity of a problem can be determined by transforming the problem to another problem with known complexity. To show that problem P is at least as hard as another problem Q with a known lower bound, we need to reduce Q to P. Then a lower bound for Q will be a lower bound for P.