Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
    
What is $n$ exactly? What variables is the polynomial in/over? – Raphael Mar 14 at 13:18
up vote 12 down vote accepted

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.

share|cite|improve this answer
1  
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 at 11:10
2  
It comes from $\sum_{i=1}^n (2^in)^2 = \Theta(4^nn^2)$. – Yuval Filmus Mar 14 at 11:15
    
@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. – Yakk Mar 14 at 15:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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