0

I have a few questions regarding complexity:

  • How do you name this complexity: $ f(M,D) = O(M^D) $. Is it f is exponential in D and what exactly in M, polynomial?

  • Just to confirm $ f(M,D) = O(MD)$ is linear in both M and D, right?

  • Also is $f(M,D) = O(M^2D + M^2) = O(M^2D)$?

Thanks!

Marco Goretti
  • 1
  • Yes, yes, and (yes if $D = \Omega(1)$). For the first, it is often the case in a problem there is a "dominant parameter" and then maybe some others (i.e., one that is seen as more stringent than the other): here, if $M$ is the dominant parameter and $D$ is seen as a constant (think for instance as $D$ being the dimension, but $M$ is the range of each coordinate), then it is polynomial in $M$ (with an explicit, exponential dependence on $D$); if the dimension is the thing that matters (e.g., for Boolean functions ${0,1}^D\to {0,1}$, $M=2$ and $D\to\infty$), then is it exponential in $D$. – Clement C. Jan 03 '15 at 13:17
  • Thanks! And what about $MD^2 + D^3$. What's the general way of naming it? – Marco Goretti Jan 03 '15 at 13:27
  • If no relation is known between $M$ and $D$, I don't think there is a good name: you have to keep both terms. – Clement C. Jan 03 '15 at 15:42

0 Answers0