10 Computational Complexity

S. Sridhar

This module 31 focuses on introducing theory of computational complexity. The module discusses how to find limitations of algorithms in terms of upper and lower bounds. The module also discusses the ways of finding lower bound of the algorithms. The objectives of this module are

 

·         To understand the concept of Computational Complexity

·         To Understand Upper bound theory

·         To Understand Lower Bound Theory

·         To know about Proof of Lower Bound Theory

 

Computational Complexity

 

There are two types of complexity theory. One is related to algorithm complexity analysis called algorithmic complexity theory and another related to problems called computational complexity theory.

 

Algorithmic complexity theory aims to analyze the algorithms in terms of the size of the problem. In modules 3 and 4, we had discussed about these methods. The size is the length of the input. It can be recollected from module 3 that the size of a number n is defined to be the number of binary bits needed to write n. For example, Example: b(5) = b(1012) = 3. In other words, the complexity of the algorithm is stated in terms of the size of the algorithm.

 

Asymptotic Analysis refers to the study of an algorithm as the input size reaches a limit and analyzing the behaviour of the algorithms. The asymptotic analysis is also science of approximation where the behaviour of the algorithm is expressed in terms of notations such as big-oh, Big-Omega and Big- Theta.

 

Computational complexity theory is different. Computational complexity aims to determine lower bound on the efficiency of all the algorithms for a given problem and Computational complexity is measured independently of the implementation. In simple words, computational complexity is about the problem and not the algorithm. In computational complexity theory, two things are important. One is the upper bound and another is the lower bound of the algorithm. Lower and upper bounds defines the limits of the algorithm. Upper bound indicates the worst case performanc e of the algorithm and lower bound indicates the best case performance of the given algorithm.

 

Uppe r bound of the Algorithm

 

Upper bound of the algorithm is the pessimistic view of the algorithm. It can be used to indicate worst, average and best case analysis of the algorithm and often expressed as a function. It can be viewed as a proof that the given problem can be solved using at most ‘n’ operations, even in the worst case.

 

The upper bound for an algorithm is used to indicate the upper or highest growth rate. Normally the algorithm is measured with respect to best, worst and average case analysis. It can be said based on literature [1,2,3] that “the running time grows at most this much, but it could grow more slowly”.

 

In other words, the cost also is represented as a function. How to determine the upper bound of an algorithm? Let A be the algorithm to be analyzed and if In is set of all possible inputs to Algorithm A and fA (I) is the resource cost of the algorithm when given input I ranges over In . Then, the following costs can be defined:

 

 

worst cost (A) = max I  Î In  fA(I)

 

Best  cost (A) = min I Î In   fA(I)

 

 

One can say the upper bound of the algorithm succinctly using Big-oh notation [4]. It can be described for run time T(n) of the given algorithm as follows: Let T(n) a non-negatively valued function, then T(n) is in set O(ƒ(n)) if there exists two positive constants c and n0 such that T(n)

 

≤ cƒ (n) for all n > n0. Here,   and .

 

For example, for towers of Hanoi, the upper bound is is given as f(n) = 2n-1. One can verify that by substituting different values for ‘n’ and verify it matches with the number of disks movement to move dist from source peg to destination peg. This is shown in table 1.

 

 

From this one can guess, that the upper bound is 2n-1.

 

One can also recollect from modules 3, 4 and 5, we called this as mathematical Induction and using which the upper bound is correctly established.

 

 

Lower Bound Theory

 

Lower bound is for problems and finding it is difficult compared to upper bound of the algorithm. Lower bound is the smallest number of operations necessary to solve a problem over all inputs of size n. In short, it is “At least this much work to be done” [2,3].

 

Lower bound is an indication of how hard the algorithm is! It is done for problems and not algorithms. In other words, it is obtained the “best’ algorithms that is required to solve the given problem. Let M be the model, and if Am is the set of all algorithms for problem P, then the Lower bound on the worst cost of P is given as follows:

 

min A belongs Am { max fA(I)}

 

Some of the examples of the lower bound are given as follows:

  1. Number of comparisons needed to find the largest element in a set of n numbers
  2. Number of comparisons needed to sort an array of size n
  3. Number of comparisons necessary for searching in a sorted array
  4. Number of multiplications needed to multiply two n-by-n matrices

 

Lower bound for an algorithm with run time T(n) is given formally as follows:

 

 

T(n) a non-negatively valued function, T(n) is in set Ω(ƒ(n)) if there exists two positive constants c and n0 such that T(n) ≥ cƒ(n) for all n > n0.

 

 

Lower bounds can be of two types.

 

•      Worst Case Lower bound

•      Average case Lower bound

 

 

It must be observed that the actual cost is in between Upper and Lower bound and lower bound indicates how optimal the algorithm is! A best scenario is lower bound = upper bound or nearly equal and if not, then better search for solution continues.

 

Let us discuss about sorting problems where these theories can be applied.

 

 

Sorting proble ms

 

There are two models for finding bounds for sorting problems. They are

  •  Exchange Model
  • Comparison model

Let us discuss about them now.

 

Exchange Model

 

In exchange model, the input consists of ‘n’ items and the only operation allowed is exchange at a cost of 1 step [2,3]. All other operations like comparison, examining item is considered as cost free operations. In exchange model, n-1 exchanges are required. Therefore, the upper Bound is n-1 exchanges are sufficient and for lower bound, n-1 Exchanges are necessary in the worst case . In short, n-1 represents the cost required for lower and upper bound.

 

Comparison Model

 

In comparison model, the important operation is comparison operations [3]. In this model, the input consists of ‘n’ items and the only operation allowed is comparison information as yes / No. Apart from comparison operation, all other operations such as exchange is cost free

 

Let us apply comparison model for finding lower and upper bounds.

 

 

Finding Maximum in an array

 

Given an array, the problem is to find maximum element. One can easily find that, the upper bound is n-1 as at most n-1 comparisons are sufficient to find maximum of n elements. Similarly, the lower bound is n-1 as n-1 comparisons are necessary in worst case to find the maximum of n elements. In short, finding the maximum element in an array is a linear algorithm of complexity O(n).

 

 

Finding the second largest element in Array

 

Finding the second largest element in an array is an interesting problem. This problem could be solved by sorting the elements using a sorting algorithm. This requires a time of O(n log n). Instead, a better algorithm can be found. This is done by a method called tournament method and is shown Fig. 1 for 8 elements.

 

How many comparisons are required?

 

Finding upper bound is easy as n-1 comparisons are sufficient to find maximum of n elements. What about lower bound? It can be recollected from divide and conquer discussion for this problem, 2n-3 comparisons are necessary in worst case to find the maximum of n elements. For example, the largest element requires n-1 comparison, the next largest of the remainder requires n-2 comparisons. In total, 2n-3 comparisons are required.

 

 

Lower Bound finding methods:

 

There are various methods for finding the lower bound. In this module, two techniques are discussed. They are

 

1.  Trivial lower bounds

 

2.    Information-theoretic arguments (decision trees)

 

 

Let us discuss about them now.

 

Trivial Lowe r Bounds

 

Based on counting the number of items that must be processed in input and generated as output [2,3]. This is a very primitive method and can be applied to a small set of problems. For example, consider the problem of finding maximum element in array. It requires n steps or n/2 comparisons at most. This is the trivial bound.

 

 

Decision Tree

 

Decision tree is an information theoretic method. It is very popular [1,3,4]. Decision Tree is a convenient model of algorithms involving comparisons in which the internal nodes represent comparisons and the leaves represent outcomes (or input cases).

Let us consider a sorting problem of six elements. This is given in Fig. 2.

 

In decision tree model, to find the lower bound, we have to find the smallest depth of a binary tree. Based on Fig 2 for six elements, one can easily verify that for ‘n’ elements, there will be n! distinct permutations and there would be n! leaf nodes in the binary decision tree.

 

In a balanced tree has the smallest depth:

 

 

 

Summary

 

One can conclude from this module that

 

  • Upper bound indicates maximum number of Operations needed.
  • Lower bound indicate smallest number of operations required to compute
  • Establishing upper and lower bound is must
  • Proof techniques are important to establish upper and Lower bounds.

 

References:

 

  1. S.Sridhar , Design and Analysis of Algorithms , Oxford University Press, 2014.
  2. A.Levitin, Introduction to the Design and Analysis of Algorithms, Pearson Education, New Delhi, 2012.
  3. T.H.Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.
  4. K.S.Easwarakumar, Design and Analysis of Algorithms, MCA Text, Anna University.