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.

  • $\begingroup$ "Exponential in $n$" means "exponential when considered as a function of $n$". For example, $ce^n$ is exponential in $n$, but linear in $c$. $\endgroup$ – Bungo Nov 1 '17 at 16:28
  • $\begingroup$ @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$ $\endgroup$ – ng.newbie Nov 1 '17 at 16:32
  • $\begingroup$ 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$). $\endgroup$ – Bungo Nov 1 '17 at 16:35
  • $\begingroup$ @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$. $\endgroup$ – ng.newbie Nov 1 '17 at 16:42
  • $\begingroup$ 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$. $\endgroup$ – Bungo Nov 1 '17 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.