# What does the phrase “exponential in n” mean ?

I am trying to make sense of the running time of certain algorithms, but a phrase keeps coming up like "n is exponential in S" or "n is polynomial in S".

What does that mean ?

What does it mean that a variable is exponential "in" another variable ?

A layman's explanation with some examples would greatly be appreciated.

• "Exponential in $n$" means "exponential when considered as a function of $n$". For example, $ce^n$ is exponential in $n$, but linear in $c$. – Bungo Nov 1 '17 at 16:28
• @Bungo Yeah but the overall function is not linear. So why would you even say that ? I mean I can see that function is overall exponential, if I am not wrong, then why would you say that it is linear in $c$ – ng.newbie Nov 1 '17 at 16:32
• If you consider it as a function of two variables, $c$ and $n$, then it's exponential in $n$ (i.e. when we hold $c$ constant and vary $n$). And it's linear in $c$ (i.e. when we hold $n$ constant and vary $c$). – Bungo Nov 1 '17 at 16:35
• @Bungo So just to test my understanding - if a function is composed of $n$ variables and $p$ of those variables are exponential we can say that the function is exponential in those $p$ variable while not exponential in the remaining, provided $p$ < $n$. – ng.newbie Nov 1 '17 at 16:42
• Yes, that's right. For example, $c 2^a 3^b e^x k^2$ is exponential in $a$, $b$, and $x$, but it's linear in $c$ and quadratic (polynomial) in $k$. – Bungo Nov 1 '17 at 16:44