1
$\begingroup$

I have an algorithm with three variables affecting the time complexity: $k$, $L$, and $n$. I have come up with the following that expresses the complexity:

$O(kn + k^2L + k^2nL + knL)$

I think I should be able to simplify this to:

$O(k^2nL)$

Am I correct? I'm a little fuzzy on how to simplify things when working with multiple variables, but it seems right that since every other term is a factor of $k^2nL$, it should dominate the other terms?

$\endgroup$
  • $\begingroup$ Yes, this seems right, assuming all parameters are integers. $\endgroup$ – Yuval Filmus Feb 15 '18 at 6:45
  • $\begingroup$ (By integers, I meant positive integers.) $\endgroup$ – Yuval Filmus Feb 15 '18 at 7:38
  • $\begingroup$ @YuvalFilmus, and by positive integers you mean real numbers greater than 1, right? ;) $\endgroup$ – Peter Taylor Feb 15 '18 at 8:31
  • $\begingroup$ @PeterTaylor While it's true that the results hold whenever $k,n,L \geq c$ for some constant $c>0$, in practice it is usually the case that $k,n,L$ are positive integers. $\endgroup$ – Yuval Filmus Feb 15 '18 at 8:45
  • 1
    $\begingroup$ "I'm a little fuzzy on how to simplify things when working with multiple variables" -- good instinct; the usual definitions fail miserably for multiple (independent) variables. See also here and here (and some questions linking there). $\endgroup$ – Raphael Feb 15 '18 at 9:35
1
$\begingroup$

Suppose that there exists a strictly positive constant $c > 0$ such that $k,n,L \geq c$; this happens for example if $k,n,L$ are all positive integers. In this case, a function is in $O(kn + k^2L + k^2nL + knL)$ iff it is in $O(k^2nL)$, where for our purposes $f(k,n,L) = O(g(k,n,L))$ (read: $f(k,n,L)$ is in $O(g(k,n,L))$) if there exists a constant $C>0$ such that for all $k,n,L$ "in range" we have $f(k,n,L) \leq C g(k,n,L)$. Here "in range" is the common domain of the functions $f,g$, such as all positive integers or all positive reals which are at least $c$, for some positive $c>0$.

$\endgroup$
  • $\begingroup$ $c$ should be greater than $1$ - or, at least, the interpretation which should be given to $O(c + c^2)$ changes when $c$ crosses $1$. $\endgroup$ – Peter Taylor Feb 15 '18 at 10:06
  • $\begingroup$ Why? If $x \geq c > 0$ then $x = O(x^2)$ just as well, with the hidden constant depending on $c$. $\endgroup$ – Yuval Filmus Feb 15 '18 at 10:26
  • $\begingroup$ Because the same notation is used inconsistently for different asymptotics which are understood from the context. E.g. in mathematics I see $O(x^2)$ used more often for the asymptotic behaviour as $x \to 0$ rather than $x \to \infty$. $\endgroup$ – Peter Taylor Feb 15 '18 at 10:54
  • $\begingroup$ Thanks, I think I understand how this follows the definition of the $O()$ notation. I'm still uncertain how I can verify the existence of $C$ in practice, but I guess that would just take trying out some more examples. I suppose if I had $O(k^2n+kn^2)$, then I could simplify it further to $O(k^2+n^2)$ because there is a $C > n,k$? Also, it seems you are referring to a single $C$ and not several $C_k,C_n,C_L$ as you hold some of the variables constant while varying one at a time? $\endgroup$ – xdhmoore Feb 25 '18 at 0:18
  • $\begingroup$ The simplification you suggest is invalid. Think of what happens when $k=n$. $\endgroup$ – Yuval Filmus Feb 25 '18 at 6:03

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.