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$
6
  • $\begingroup$ Yes, this seems right, assuming all parameters are integers. $\endgroup$ Commented Feb 15, 2018 at 6:45
  • $\begingroup$ (By integers, I meant positive integers.) $\endgroup$ Commented Feb 15, 2018 at 7:38
  • $\begingroup$ @YuvalFilmus, and by positive integers you mean real numbers greater than 1, right? ;) $\endgroup$ 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$ 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$ 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$ 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$ 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$ 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$ Commented Feb 25, 2018 at 0:18
  • $\begingroup$ The simplification you suggest is invalid. Think of what happens when $k=n$. $\endgroup$ Commented Feb 25, 2018 at 6:03

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.