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

<p>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.</p>

<p>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).</p>

CC BY-SA 3.0
2011-04-20T21:20:02.053Z
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!
justausr
CC BY-SA 3.0
2011-04-20T21:03:50.880Z
2011-04-20T21:03:50.880Z
Antonio Valerio Miceli-Barone
<p>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?</p>

<p>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"</p>

<p>Examples: </p>

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

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

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

<cc.complexity-theory><complexity-classes>
Function input to output size relationship. What is it? Any notable research on it?
justausr
# Function input to output size relationship. What is it? Any notable research on it?

(Asked by: username_0 on 2011-04-20)

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.

**Tags:** cc.complexity-theory, complexity-classes

---

## 1 answers

### Answer by username_1 on 2011-04-20. Score: 4 | Accepted answer

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).

> **Comments:**
> **username_0**: 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!  

---

