3 ms·
> If you have a sequence of programs with polynomial runtime, but which grows as N, N^2, N^3, N^4, ..., that's a textbook example of exponential growth No, it
by whatyoucantsay 9y ago
> If you have a sequence of programs with polynomial runtime, but which grows as N, N^2, N^3, N^4, ..., that's a textbook example of exponential growth
No, it isn't. N, N^2, N^3, N^4, ... is polynomial, not exponential. Exponential would be X^N. Look at the graph on the Wikipedia page I linked to.
- yorwba 9y agoEach element of the sequence is a polynomial, but the sequence of polynomials grows exponentially. X^N is exponential in N, polynomial in X. N^X is exponential in X, polynomial in N.
- whatyoucantsay 9y ago> Each element of the sequence is a polynomial, but the sequence of polynomials grows exponentially. Bringing this back to the original comment about nesting loops, perhaps what you're describing is some sort of metaprogramming that dynamically generates increasingly deeply nested loops based upon the size of the input. If someone were to write that program then yes, it would be exponential. In the far more common case of a programmer nesting a few loops, the resulting run-time would be polynomial, not exponential.
- IncRnd 9y agoWhat you are describing now is called superpolynomial time in computer science.