Editing Computational complexity theory (section)

===Measuring the size of an instance===
To measure the difficulty of solving a computational problem, one may wish to see how much time the best algorithm requires to solve the problem. However, the running time may, in general, depend on the instance. In particular, larger instances will require more time to solve. Thus the time required to solve a problem (or the space required, or any measure of complexity) is calculated as a function of the size of the instance. The input size is typically measured in bits. Complexity theory studies how algorithms scale as input size increases. For instance, in the problem of finding whether a graph is connected, how much more time does it take to solve a problem for a graph with <math>2n</math> vertices compared to the time taken for a graph with <math>n</math> vertices?

If the input size is <math>n</math>, the time taken can be expressed as a function of <math>n</math>. Since the time taken on different inputs of the same size can be different, the worst-case time complexity <math>T(n)</math> is defined to be the maximum time taken over all inputs of size <math>n</math>. If <math>T(n)</math> is a polynomial in <math>n</math>, then the algorithm is said to be a [[polynomial time]] algorithm. [[Cobham's thesis]] argues that a problem can be solved with a feasible amount of resources if it admits a polynomial-time algorithm.