1.Previous
3.Next

with a Turing machine is defined as the function , where is the maximum number of steps that takes on any input of length .

In computational complexity theory, theoretical computer scientists are concerned less with particular runtime values and more with the general class of functions that the time complexity function falls into. For instance, is the time complexity function a polynomial? A logarithmic function? An exponential function?

1.Previous
3.Next