Added to Favorites

Related Searches

Definitions

Nearby Words

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, fg, and 2^{f}, are also proper complexity functions.

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

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday November 21, 2006 at 19:10:42 PST (GMT -0800)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday November 21, 2006 at 19:10:42 PST (GMT -0800)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.