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?

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

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
5
  • $\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
    Commented 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$
    – Yuval Filmus
    Commented 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$
    – Peter Taylor
    Commented 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
    Commented Feb 25, 2018 at 0:18
  • $\begingroup$ The simplification you suggest is invalid. Think of what happens when $k=n$. $\endgroup$
    – Yuval Filmus
    Commented Feb 25, 2018 at 6:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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