1
$\begingroup$

I wounder why the complexity of algorithms always depend on the size of the input, but not on the size of the output.

For example, in a problem that I have solve, the size of the input is exponentially smaller than the size of output. In addition, the complexity of the algorithm is polynomial by the size of the output, and pseudo-polynomial by the size of the input.

I think that in such case, the complexity of algorithm is said to be "polynomial", but I am not sure about it.

What are your opinion?

Improve this question
$\endgroup$
2
  • $\begingroup$ Usually complexity of decision problems is measured. Since every decision problem takes only 1 bit, the concept is useless. $\endgroup$
    – rus9384
    Sep 27, 2017 at 14:54
  • 2
    $\begingroup$ Often the output size is polynomial in the input size, and so it doesn't matter. In cases where it does matter, such as in enumeration problems, people do care about polynomial time with respect to the output size. $\endgroup$
    – Yuval Filmus
    Sep 27, 2017 at 16:19

2 Answers 2

Reset to default
1
$\begingroup$

I wonder why the complexity of algorithms [does not] depend on the size of [...] the output.

But it does!

The size of the input is often used as a trivial lower bound on the running time ("you need to write the output"). So trivial, indeed, that it's rarely talked about in introductory courses. There, the output is usally not the dominating factor so it's not interesting to discuss is further.

Think about what that would mean on the intuitive: an algorithm that writes more bits than it takes time to compute them. That doesn't seem very efficient in itself; maybe your output encoding is bad.

That said, you do on occasion encounter runtime analyses where characteristics of the output appear in the determined bounds. Search and enumeration algorithms, for instance, can admit non-trivial bounds the separate them from brute force ("I don't have to check all candidates, but only at most three times the number of those I want to find").

Improve this answer
$\endgroup$
0
$\begingroup$

It doesn't always depend on input size. In the subject of Kolmogorov complexity and other information theory problems (using computability theory to describe how much information is in data) the relevant counting is often in reference to the output instead. Example, a string of length $n$ which can be output by a Turing Machine given an input of length $\log n$ would be a demonstration of the output having been compressed to a modest amount of information which when given as input produces the desired output. Your "zip file" if you like. Evidently the definition here prefers one begin with the output size and model the possible input sizes. For example, a string is Kolmogorov-random if it takes a longer string of input to produce the output.

Improve this answer
$\endgroup$
1
  • $\begingroup$ In that case the complexity still depends on input (needs to be read) and the change described is only polynomial, discarded by OP in the question. $\endgroup$
    – Evil
    Jul 2, 2018 at 6:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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