I wrote an article titled “Exponential Optimizing” for Game Developer, and since it was published a few people wrote to tell me that what I was describing was not exponential, but was actually polynomial.
They are quite correct. I had mistakenly used “exponential” in the sense of “rapidly increasing”, which is a valid usage, but not too helpful in discussing algorithms.
To be clear, for a variable x, and a constant c,
x^c is polynomial
c^x is exponential.
This is confused a little by the use of n for the variable (as in the number of elements), as n is usually constant.
That’s not quite it either.
If c is not constrained to be an integer x^c is refered to more properly as a power function. If c is an integer and you want to stress that it’s only one term you can refer to it as a monomial.
Comment by Soylent — April 23, 2008 @ 1:43 pm
n is not used for a constant; rather for working with the set of positive integers.
Comment by me — May 28, 2008 @ 7:25 am