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.

**Lower-Bound Arguments**

We can look at the efficiency
of an algorithm two ways. We can establish its asymp-totic efficiency class
(say, for the worst case) and see where this class stands with respect to the
hierarchy of efficiency classes outlined in Section 2.2. For exam-ple, selection
sort, whose efficiency is quadratic, is a reasonably fast algorithm, whereas
the algorithm for the Tower of Hanoi problem is very slow because its
ef-ficiency is exponential. We can argue, however, that this comparison is akin
to the proverbial comparison of apples to oranges because these two algorithms
solve different problems. The alternative and possibly “fairer” approach is to
ask how efficient a particular algorithm is with respect to other algorithms
for the same problem. Seen in this light, selection sort has to be considered
slow because there are ** O(n** log

When we want to ascertain the
efficiency of an algorithm with respect to other algorithms for the same
problem, it is desirable to know the best possible efficiency *any *algorithm solving the problem may
have. Knowing such a* lower bound *can

In this section, we present
several methods for establishing lower bounds and illustrate them with specific
examples. As we did in analyzing the efficiency of specific algorithms in the
preceding chapters, we should distinguish between a lower-bound class and a
minimum number of times a particular operation needs to be executed. As a rule,
the second problem is more difficult than the first. For example, we can
immediately conclude that any algorithm for finding the median of ** n** numbers must be in

**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. Since any algorithm must at least “read” all the items it needs
to process and “write” all its outputs, such a count yields a *trivial*** lower
bound**. For example, any algorithm for generating all permutations of

As another example, consider
the problem of evaluating a polynomial of degree *n*

** p(x) **=

at a given point ** x**, given its coefficients

In a similar vein, a trivial
lower bound for computing the product of two ** n **×

Trivial lower bounds are
often too low to be useful. For example, the trivial bound for the traveling
salesman problem is * (n*^{2}** ),** because its input is

There is another obstacle to
deriving a meaningful lower bound by this method. It lies in determining which
part of an input must be processed by any algorithm solving the problem in
question. For example, searching for an ele-ment of a given value in a sorted
array does not require processing all its elements (why?). As another example,
consider the problem of determining connectivity of an undirected graph defined
by its adjacency matrix. It is plausible to expect that any such algorithm
would have to check the existence of each of the ** n(n** − 1

**Informatikon-Theoretic
Arguments**

While the approach outlined
above takes into account the size of a problem’s output, the
information-theoretical approach seeks to establish a lower bound based on the
amount of information it has to produce. Consider, as an example, the
well-known game of deducing a positive integer between 1 and ** n** selected by somebody by asking that person
questions with yes/no answers. The amount of uncertainty that any algorithm
solving this problem has to resolve can be measured by log

The approach we just
exploited is called the ** information-theoretic argument**
because of its connection to information theory. It has proved to be quite
useful for finding the so-called

**Adversary
Arguments**

Let us revisit the same game
of “guessing” a number used to introduce the idea of an information-theoretic
argument. We can prove that any algorithm that solves this problem must ask at
least log_{2} ** n** questions in its worst case
by playing the role of a hostile adversary who wants to make an algorithm ask
as many questions as possible. The adversary starts by considering each of the
numbers between 1 and

This example illustrates the ** adversary
method** for establishing lower bounds. It is based on following the
logic of a malevolent but honest adversary: the malev- olence makes him push
the algorithm down the most time-consuming path, and his honesty forces him to
stay consistent with the choices already made. A lower bound is then obtained
by measuring the amount of work needed to shrink a set of potential inputs to a
single input along the most time-consuming path.

As another example, consider
the problem of merging two sorted lists of size *n*

*a*_{1}* < a*_{2}* < *^{. . .}* < a***_{n}** and

into a single sorted list of
size 2** n**. For simplicity, we assume
that all the

Is there an algorithm that
can do merging faster? The answer turns out to be no. Knuth [KnuIII, p. 198]
quotes the following adversary method for proving that 2** n** − 1 is a lower bound on the number of key
comparisons made by any comparison-based algorithm for this problem. The
adversary will employ the following rule: reply true to the comparison

*b*_{1}* < a*_{1}* < b*_{2}* < a*_{2}* < *^{. . .}* < b*_{n}* < a*_{n}*.*

To produce this combined
list, any correct algorithm will have to explicitly com-pare 2** n** − 1 adjacent pairs of its elements, i.e.,

*b*_{1}* < b*_{2}* < a*_{1}* < a*_{2}* < *^{. . .}* < b*_{n}* < a*_{n}*,*

which is consistent with all
the comparisons made but cannot be distinguished from the correct configuration
given above. Hence, 2** n** − 1 is, indeed, a lower bound for the number of
key comparisons needed for any merging algorithm.

**Problem
Reduction**

We have already encountered
the problem-reduction approach in Section 6.6. There, we discussed getting an
algorithm for problem ** P** by reducing it to another
problem

We will establish the lower
bounds for sorting and searching in the next sec-tion. The element uniqueness
problem asks whether there are duplicates among ** n** given numbers. (We encountered this problem in
Sections 2.3 and 6.1.) The proof of the lower bound for this seemingly simple
problem is based on a very sophisti-cated mathematical analysis that is well
beyond the scope of this book (see, e.g., [Pre85] for a rather elementary
exposition). As to the last two algebraic prob-lems in Table 11.1, the lower
bounds quoted are trivial, but whether they can be improved remains unknown.

As an example of establishing
a lower bound by reduction, let us consider the ** Euclidean minimum spanning tree
problem**: given

Since the final results about
the complexity of many problems are not known, the reduction technique is often
used to compare the relative complexity of prob-lems. For example, the formulas

show that the problems of
computing the product of two ** n**-digit integers and squaring
an

There are several similar
results for matrix operations. For example, multi-plying two symmetric matrices
turns out to be in the same complexity class as multiplying two arbitrary
square matrices. This result is based on the observation that not only is the
former problem a special case of the latter one, but also that we can reduce
the problem of multiplying two arbitrary square matrices of order ** n**, say,

where *A***^{T}** and

from which the needed product
** AB** can be easily extracted.
(True, we will have to multiply matrices twice the original size, but this is
just a minor technical complication with no impact on the complexity classes.)

Though such results are
interesting, we will encounter even more important applications of the
reduction approach to comparing problem complexity in Sec-tion 11.3.

**Exercises 11.1**

**
**Prove that any algorithm solving the alternating-disk puzzle
(Problem 14 in Exercises 3.1) must make at least ** n(n** + 1

**
**Prove that the classic recursive algorithm for the Tower of Hanoi
puzzle (Section 2.4) makes the minimum number of disk moves needed to solve the
problem.

**
**Find a trivial lower-bound class for each of the following problems
and indi-cate, if you can, whether this bound is tight.

**
**finding the largest element in an array

**
**checking completeness of a graph represented by its adjacency
matrix

**
**generating all the subsets of an ** n**-element set

**
**determining whether ** n** given real numbers are all
distinct

**
**Consider the problem of identifying a lighter fake coin among ** n** identical-looking coins with the help of a
balance scale. Can we use the same information-theoretic argument as the one in
the text for the number of ques-tions in the guessing game to conclude that any
algorithm for identifying the fake will need at least log

Prove that any
comparison-based algorithm for finding the largest element of an ** n**-element set of real numbers must make

**
**Find a tight lower bound for sorting an array by exchanging its
adjacent elements.

**
**Give an adversary-argument proof that the time efficiency of any
algorithm that checks connectivity of a graph with ** n** vertices is in

**
**What is the minimum number of comparisons needed for a
comparison-based sorting algorithm to merge any two sorted lists of sizes ** n** and

Find the product of matrices ** A** and

**
****a. **Can one use this section’s
formulas that indicate the complexity equiva-lence of multiplication and
squaring of integers to show the complexity equivalence of multiplication and
squaring of square matrices?

**
**Show that multiplication of two matrices of order ** n** can be reduced to squaring a matrix of order 2

**
**Find a tight lower-bound class for the problem of finding two
closest numbers among ** n** real numbers

**
**Find a tight lower-bound class for the number placement problem
(Problem 9 in Exercises 6.1).

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Limitations of Algorithm Power : Lower-Bound Arguments |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.