Unit 13 Limitations of Algorithm Power
Structure:
13.1 Introduction
Objectives
13.2 Lower Bound Arguments
Trivial lower bounds
Information theoretic arguments
Adversany arguments
Problem reduction
13.3 Decision Trees
Decision trees for sorting algorithms
Decision trees for searching a sorted array
13.4 P, NP and NP -
Complete Problems
Non deterministic algorithm
NP hard and NP complete classes
-
Cook's theorem
13.5 Summary
13.6 Glossary
13.7 Terminal Questions
13.8 Answers
13.1 Introduction
So far in the previous units we have studied many algorithms, and learnt
how they play a significant role in solving a range of problems. But, it is not
possible to solve all problems using algorithms. The power of algorithms is
limited to some extent.
The reasons for these limitations are
Some problems which can be solved using algorithms are not solved
within polynomial time.
Even if we can solve some problems within the polynomial time, the
is in lower bound.
efficiency of the algorithm
This unit covers the limitations or algorithm power with respect to lower-
bound arquments of algorithms. It explains decision trees with examples. It
also analyzes P, NP and NP-complete problems.
,Objectives:
be able to:
studying this unit you should
After
algorithms
explain the lower-bound arguments of
trees
describe and implement decision
define P, NP and NP-complete problems
13.2 Lower - Bound Arguments
In this section we will discuss about the lower bound arguments in
algorithms. Lower-bound means calculating the minimum amount of work
required to solve the problem. While obtaining the lower-bound of the
algorithm we look for the limits of efficiency of any algorithm that can solve
the problem.
The following two methods help to make an algorithm more efficient:
1) First we verify the asymptotic efficiency class of the algorithm.
2) Then we check the class of the given problem to see where it fits in the
hierarchy of the eficiency classes (i.e., whether the problem lies in
linear, quadric, logarithmic or exponential category of efficiency class).
The efficiency of different algorithms is given in the table 13.1.
Table 13.1: Efficiency of Different Algorithms
Algorithms Efficiency
Insertion sort n
Quick sort n log n
Heap sot n log n
Linear search n/2
Binary search log 2 n
When we are finding the efficiency of an algorithm, it is better to compare it
with those algorithms that are used to solve similar kind of problems. For
example if we want to determine the efficiency of insertion sort then we have
to compare it with other sorting methods. We cannot determine the
efficiencyof insertion sort if we compare it with
the efficiency of Tower o
Hanoi problem because these are two different
types of problems.
When we are determining the efficiency of an
algorithm with respect to otn
algorithms that are used to solve the same problem, it is better to the
best posible efticiency of an algorithm which can
Know
solve that prooie
, Knowing tnis helps us to improve the algorithm. If there is a gap beiwee
the best lower bound and the fastest algorithm then there is a possibility o
improving the algorithm i.e. either there is an algorithm with the fastest
lower-bound or we can prove the better lower-bound for that algorithm can
be established.
Following are the different methods for obtaining the lower-bound of an
algorithm:
Trivial lower bounds
Information theoretic arguments
Adversary arguments
Problem reduction
13.2.1 Trivial lower bounds
This is the simple method used for obtaining lower bound class of an
algorithm. Trivial lower bound is obtained by counting the input data that the
algorithm reads and the output that it produces.
For example,
the trivial lower bond for
generating all permutation ofn
numbers will be Q(n!) because the output size here is factorial n. This
algorithm is tight because good algorithms for generating permutations
spend a constant time on each of them expect the initial one.
Similarly if
calculate the trivial lower bound for finding the
we
product of two
n x n matrices, it is Q(n^). This is because this
algorithm takes two n
elements as the inputs and produces n elements as
output. It is still not
known whether this bond is tight.
Limitations of this method
Trivial lower bounds are less useful. For instance let us
consider the
problem of traveling salesman. we see that the trivial lower bound for
this
algorithm is Q(n) as the algorithm hasn (n-1)/2 distances as the input and
producesn+1 cities as the output. This trivial lower
bound is not useful in
this case because there is no similar problem to
compare it with.
There is one more problem in obtaining the lower-bound
using this method.
When we are finding the lower-bound of an algorithm
using this method it is
necessary to determine which part of the input has to be processed. For
instance, searching an element in the sorted array does not
require
processing of all the input elements.
Structure:
13.1 Introduction
Objectives
13.2 Lower Bound Arguments
Trivial lower bounds
Information theoretic arguments
Adversany arguments
Problem reduction
13.3 Decision Trees
Decision trees for sorting algorithms
Decision trees for searching a sorted array
13.4 P, NP and NP -
Complete Problems
Non deterministic algorithm
NP hard and NP complete classes
-
Cook's theorem
13.5 Summary
13.6 Glossary
13.7 Terminal Questions
13.8 Answers
13.1 Introduction
So far in the previous units we have studied many algorithms, and learnt
how they play a significant role in solving a range of problems. But, it is not
possible to solve all problems using algorithms. The power of algorithms is
limited to some extent.
The reasons for these limitations are
Some problems which can be solved using algorithms are not solved
within polynomial time.
Even if we can solve some problems within the polynomial time, the
is in lower bound.
efficiency of the algorithm
This unit covers the limitations or algorithm power with respect to lower-
bound arquments of algorithms. It explains decision trees with examples. It
also analyzes P, NP and NP-complete problems.
,Objectives:
be able to:
studying this unit you should
After
algorithms
explain the lower-bound arguments of
trees
describe and implement decision
define P, NP and NP-complete problems
13.2 Lower - Bound Arguments
In this section we will discuss about the lower bound arguments in
algorithms. Lower-bound means calculating the minimum amount of work
required to solve the problem. While obtaining the lower-bound of the
algorithm we look for the limits of efficiency of any algorithm that can solve
the problem.
The following two methods help to make an algorithm more efficient:
1) First we verify the asymptotic efficiency class of the algorithm.
2) Then we check the class of the given problem to see where it fits in the
hierarchy of the eficiency classes (i.e., whether the problem lies in
linear, quadric, logarithmic or exponential category of efficiency class).
The efficiency of different algorithms is given in the table 13.1.
Table 13.1: Efficiency of Different Algorithms
Algorithms Efficiency
Insertion sort n
Quick sort n log n
Heap sot n log n
Linear search n/2
Binary search log 2 n
When we are finding the efficiency of an algorithm, it is better to compare it
with those algorithms that are used to solve similar kind of problems. For
example if we want to determine the efficiency of insertion sort then we have
to compare it with other sorting methods. We cannot determine the
efficiencyof insertion sort if we compare it with
the efficiency of Tower o
Hanoi problem because these are two different
types of problems.
When we are determining the efficiency of an
algorithm with respect to otn
algorithms that are used to solve the same problem, it is better to the
best posible efticiency of an algorithm which can
Know
solve that prooie
, Knowing tnis helps us to improve the algorithm. If there is a gap beiwee
the best lower bound and the fastest algorithm then there is a possibility o
improving the algorithm i.e. either there is an algorithm with the fastest
lower-bound or we can prove the better lower-bound for that algorithm can
be established.
Following are the different methods for obtaining the lower-bound of an
algorithm:
Trivial lower bounds
Information theoretic arguments
Adversary arguments
Problem reduction
13.2.1 Trivial lower bounds
This is the simple method used for obtaining lower bound class of an
algorithm. Trivial lower bound is obtained by counting the input data that the
algorithm reads and the output that it produces.
For example,
the trivial lower bond for
generating all permutation ofn
numbers will be Q(n!) because the output size here is factorial n. This
algorithm is tight because good algorithms for generating permutations
spend a constant time on each of them expect the initial one.
Similarly if
calculate the trivial lower bound for finding the
we
product of two
n x n matrices, it is Q(n^). This is because this
algorithm takes two n
elements as the inputs and produces n elements as
output. It is still not
known whether this bond is tight.
Limitations of this method
Trivial lower bounds are less useful. For instance let us
consider the
problem of traveling salesman. we see that the trivial lower bound for
this
algorithm is Q(n) as the algorithm hasn (n-1)/2 distances as the input and
producesn+1 cities as the output. This trivial lower
bound is not useful in
this case because there is no similar problem to
compare it with.
There is one more problem in obtaining the lower-bound
using this method.
When we are finding the lower-bound of an algorithm
using this method it is
necessary to determine which part of the input has to be processed. For
instance, searching an element in the sorted array does not
require
processing of all the input elements.
