Complexity theory is the study of how hard problems are to solve. It allows mathematicians to classify problems in terms of how difficult they are, because some problems are intrinsically harder than others.

How intrinsically difficult a problem is can be measured using "Big-O notation," which denotes the average requirements of the algorithm to solve the problem in terms of running time or computer memory usage, as a function of the size of the input. Algorithms are often described--in order of intrinsic complexity or difficulty--as having "constant," "n log n," "linear," "logarithmic," "polynomial," "exponential," or "factorial" complexity. For example, multiplication has polynomial complexity, denoted O(n²); solving crosswords has exponential complexity, O(26ⁿ). Big-O notation classifies problems by their "size," which for numerical problems is usually the number of digits or bits.

An "instance" of a problem is a particular case of a general problem. Sometimes...