4
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ What is $n$ exactly? What variables is the polynomial in/over? $\endgroup$ – Raphael♦ Mar 14 '16 at 13:18
12
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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)$? $\endgroup$ – Souradeep Nanda Mar 14 '16 at 11:10
  • 2
    $\begingroup$ It comes from $\sum_{i=1}^n (2^in)^2 = \Theta(4^nn^2)$. $\endgroup$ – Yuval Filmus Mar 14 '16 at 11:15
  • $\begingroup$ @YuvalFilmus Given that nothing but the largest term in that sum really matters, you can get it from a simpler argument. ;) Then again, I guess that gives little-o not big-O. $\endgroup$ – Yakk Mar 14 '16 at 15:26
  • $\begingroup$ What exactly is the naive algorithm? An algorithm using addition just does n additions. I don't understand. Relative to the input "length" (binary string?) I'm not sure how you'd determine the time complexity. $\endgroup$ – KthProg Nov 28 '17 at 18:34
  • $\begingroup$ If you did use n = length(x) = log(x), you'd have x additions, which is 2^n, not n^2... so I don't get it. $\endgroup$ – KthProg Nov 28 '17 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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