Neha Patil (Editor)

Proper complexity function

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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)) 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 function, space-constructible function, and time-constructible function.

    References

    Proper complexity function Wikipedia
    (Text) CC BY-SA