[Solved]: Give a specific case where calling a polynomial time function n times gives an exponential time algorithm

Problem Detail: 

We were asked this question in exam and I am not satisfied with the answer the teacher gave.

Let me justify my point of view. Let there be a polynomial time function having time complexity $n^{c_1}$. If we call the function polynomial times, say $n^{c_2}$ times, then the time complexity of the algorithm becomes $n^{c_1+c_2}$. Which is clearly polynomial.

Now the answer our teacher gave. Let there be a subroutine $S_i$ with time complexity $2^{i-1}n$ where $n$ is the input size. Therefore the time complexity of $S_n$ is $2^{n-1}n$. Which is exponential.

I am not satisfied with this answer because firstly the variable $i$ seems shady. We are not even calling any subroutines polynomial times, we are just assigning some value arbitrarily.

If our teacher's answer is correct could someone elaborate? If not, is there any answer to this question?

Asked By : Souradeep Nanda

Answered By : Yuval Filmus

A concrete example is repeated squaring. Squaring an integer of length $n$ takes time $O(n^2)$ (using the naive algorithm; you can do much better with more complicated algorithms). If you square an $n$-bit integer $i$ times in a row, its length becomes $2^i n$. So if you square it $n$ times in a row, the complexity is $O(4^n n^2)$, which is exponential.

The source for confusion is the input length. If the polynomial time function increases the length, then the behavior can be exponential. If it doesn't, the behavior stays polynomial.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54450