A proper complexity function is a function f mapping natural numbers to natural numbers such that:

• f is nondecreasing;

• there exists a k-string Turing machine M such that on any input of length n, M halts after O(n + f(n)) steps, uses O(f(n)) space, and outputs f(n) consecutive blanks.

If f and g are two proper complexity functions, then f+g, fg, and 2f are also proper complexity functions.

Similar notions include honest functions, space-constructible functions, and time-constructible functions.

References