Complexity class

From Wikipedia, the free encyclopedia
Jump to: navigation, search

A Complexity class is a concept from theoretical computer science and mathematics: All problems that have the same complexity are in the same complexity class. This means, that for a given input, they need about the same amount of resources, such as compute time, or memory. The most often used models for complexity are time complexity, which measures the time needed to calculate a result, or space complexity, which looks at the amount of memory or storage needed. When talking about complexity classes, a worst case scenario is usually assumed.