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 ComplexityExamples: F({1,2,3,4}) = {1,2} //where the relationship is n/2F(some 20 byte input) = 2bytes of header + 10bytes of output //the relationship is 2+n/2F(2 byte header + 10byte data) = 6 bytes output // n3/5 - 2A more concrete example would finding be the average and best input/output complexity of a compression algorithmDefining this is out of scope of my paper so I am hoping to find a definition/solution to reference.
Function input to output size relationship. What is it? Any notable research on it?
cc.complexity theory;complexity classes
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).