Randomized Algorithms (Spring 2010)/Complexity classes and lower bounds: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop No edit summary |
imported>WikiSysop No edit summary |
||
| Line 2: | Line 2: | ||
=== Upper bounds, lower bounds === | === 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. | |||
;Complexity of algorithms | |||
;Complexity of problems | |||
=== Decision problems === | === Decision problems === | ||
Revision as of 08:01, 8 January 2010
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.
- Complexity of algorithms
- Complexity of problems