# Give a specific case where calling a polynomial time function n times gives an exponential time algorithm

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?

• What is $n$ exactly? What variables is the polynomial in/over? – Raphael Mar 14 '16 at 13:18

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.
• I didnt realize, we were calling the function on the output of the previous result. That solves the problem. Can you explain how did we get $O(4^nn^2)$? – Souradeep Nanda Mar 14 '16 at 11:10
• It comes from $\sum_{i=1}^n (2^in)^2 = \Theta(4^nn^2)$. – Yuval Filmus Mar 14 '16 at 11:15