Randomized Algorithms (Spring 2010)/Complexity classes and lower bounds

Computational Models

Upper bounds, lower bounds

Bounds are just inequalities. In Computer Science, when talking about upper or lower bounds, people really mean the upper or lower bounds of complexity.

Complexity is measured by the resource costed by the computation. Our most precious resource is time (life is short!). Besides time complexity, there are other measures of complexity we may care about, including:

• space;
• communication;
• number of random bits;
• number of queries to the input;
• amount of information provided by an oracle.

There are two fundamental ways of measuring complexity

Complexity of algorithms

For an algorithm [math]\displaystyle{ A }[/math], its complexity represents its performance. Let [math]\displaystyle{ T(A,x) }[/math] be the running time of the algorithm [math]\displaystyle{ A }[/math] on input [math]\displaystyle{ x }[/math]. The worst case time complexity is given by [math]\displaystyle{ T(A)=\max_{x}T(A,x) }[/math], where the maximum is taken of the domain of the inputs with the fixed length [math]\displaystyle{ n }[/math], and [math]\displaystyle{ T(A) }[/math] is written as a function of [math]\displaystyle{ n }[/math].

Complexity of problems

The complexity of an algorithm tells how good a solution is, yet the complexity of a problem tells how hard a problem is. While the former is what we care mostly about in practice, the later is about fundamental truths of computation.