[whatyoucantsay]

> 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]

Each 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]

> 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]

What you are describing now is called superpolynomial time in computer science.