Running Time of Composition Solution – GT – Computability, Complexity, Theory: Complexity


The answer is (q(p(n))). It’s tempting to think that we run N and
then we run M. So, the total running time should
just be the sum of the two individual running times. The trouble with this,
is that it doesn’t account for the possibility that the output of N
could be much longer than the input. In fact, it could be almost p(n). Most of the program’s instructions
could have been print statements, or writes to the end of the tape for
Turing machines. So that the output of N is p(n) long and
would then take q(p(n)) time. And then that becomes
the dominant factor in our bound. In particular, this means that if both
p and q are bounded by polynomials, then the running time of the composition
will also be bounded by a polynomial, since the composition of two
polynomials is a polynomial.

Leave a Comment

Your email address will not be published. Required fields are marked *