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 applying these complexity measures, which represent two different philosophies of problem solving.
- Complexity of algorithms
- Complexity of problems