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:


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?

  • $\begingroup$ Yes, this seems right, assuming all parameters are integers. $\endgroup$ Feb 15, 2018 at 6:45
  • $\begingroup$ (By integers, I meant positive integers.) $\endgroup$ Feb 15, 2018 at 7:38
  • $\begingroup$ @YuvalFilmus, and by positive integers you mean real numbers greater than 1, right? ;) $\endgroup$ Feb 15, 2018 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$ Feb 15, 2018 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, 2018 at 9:35

1 Answer 1


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$.

  • $\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$ Feb 15, 2018 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$ Feb 15, 2018 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$ Feb 15, 2018 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, 2018 at 0:18
  • $\begingroup$ The simplification you suggest is invalid. Think of what happens when $k=n$. $\endgroup$ Feb 25, 2018 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.