# Can the following O(…) expression be simplified?

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?

• Yes, this seems right, assuming all parameters are integers. – Yuval Filmus Feb 15 '18 at 6:45
• (By integers, I meant positive integers.) – Yuval Filmus Feb 15 '18 at 7:38
• @YuvalFilmus, and by positive integers you mean real numbers greater than 1, right? ;) – Peter Taylor Feb 15 '18 at 8:31
• @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. – Yuval Filmus Feb 15 '18 at 8:45
• "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). – Raphael Feb 15 '18 at 9:35

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$.
• $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$. – Peter Taylor Feb 15 '18 at 10:06
• Why? If $x \geq c > 0$ then $x = O(x^2)$ just as well, with the hidden constant depending on $c$. – Yuval Filmus Feb 15 '18 at 10:26
• 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$. – Peter Taylor Feb 15 '18 at 10:54
• 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? – xdhmoore Feb 25 '18 at 0:18
• The simplification you suggest is invalid. Think of what happens when $k=n$. – Yuval Filmus Feb 25 '18 at 6:03