How to compute kolmogorov complexity of an algorithm?

Question

Suppose for various input strings an algorithm generates binary string with same number of 0's and 1's. The output for two different input strings may or may not be the same. Can we say anything about the space complexity of the algorithm?

Answer 1

The question isn't quite right.

Kolmogorov complexity K(x) doesn't apply to programs, it applies to a string x. More specifically, the Kolmogorov complexity of a string x is the minimum program length needed to compute a particular string x.

It has been formally proven that one can't compute the Kolmogorov complexity of a string. In practice, you can approximate via an upper bound.

The following paper by Ferbus-Zanda and Griorieff gives you the theory http://arxiv.org/abs/1010.3201

An intuitive way of thinking about such an approximate upper bound is to consider the length of a compression program that can decompress to a particular string.

Applying this to your problem, the string you describe is a random binary one, doubled. The input string acts a seed for the random number generator.

Ignoring the kolmogorov complexity part of your question, and just looking at space complexity (ie. memory footprint) aspect as @templatetypedef did, the criteria you mention are so loose that all you can say is that the lower space bound for the algorithm is O(1) and the upper bound O(n), where n is the output.