3
$\begingroup$

I'm working on a problem and I've come to a point where I need to define the input/output complexity of an algorithm. I don't remember ever studying this systematically like I did time complexity or space complexity, so what are some notable papers that deal with this problem?

Note: I'm calling it input/output complexity, but I have no idea what the actual name of this is, that would be helpful to know too! Incase it's unclear I am calling the relationship between a functions input and it's output, "Input/Output Complexity"

Examples:

  • F({1,2,3,4}) = {1,2} //where the relationship is n/2
  • F(some 20 byte input) = 2bytes of header + 10bytes of output //the relationship is 2+n/2
  • F(2 byte header + 10byte data) = 6 bytes output // n3/5 - 2

A more concrete example would finding be the average and best input/output complexity of a compression algorithm

Defining this is out of scope of my paper so I am hoping to find a definition/solution to reference.

$\endgroup$
4
$\begingroup$

I think it's improper to call this measure 'complexity'. A more apt name would be 'input to output size relation'.

Note that, strictly speaking, this is a property of the problem you are solving, not of the particular algorithm you use to solve the problem.

In the case of the compression problem, if you mean lossless compression of arbitrary binary data, then the average compression ratio is never less than 1 (and it's typically strictly greater than 1).

$\endgroup$
  • 1
    $\begingroup$ You're right, not sure where my mind was on that. Rethinking it as a property of the problem solves my issue. Although in my application the different implementations of the function may have different size outputs for the same input. The difference is constant and not polynomial. Thanks! $\endgroup$ – justausr Apr 20 '11 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.