Proper complexity function
A Proper complexity function is a function f mapping a natural number to a natural number 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)) spaces, and output s f(n) consecutive blanks.
If f and g are two proper complexity functions, then f+g, f*g, and 2^f, are also proper complexity functions.
Similar notions include honest function, space-constructible function, and time-constructible function.