2
$\begingroup$

I am computing the count of the amount of intersections between disjoint horizontal line segments and disjoint vertical line segments. The algorithm I have come up with runs in $(2n+m)\log(2n+m)$ time. I was wondering if the Big-O for this is $O((n+m)\log(n+m))$? I don't know how constants in the interior of logs with multiple variables could be bounded, if at all. How would I prove this?

$\endgroup$
2
$\begingroup$

Classical way is same as when we consider double limit $\lim\limits_{(n,m) \to \infty}f(n,m)=A$, which use intention to infinity by squares i.e. for $\forall \varepsilon>0$ $\exists \delta>0$ such that for $\forall n > \delta$ and $\forall m > \delta$ holds $|f(n,m)-A|< \varepsilon$. Using maximum norm conception we can write $\left\Vert(m,n)\right\Vert = \max\{n,m \}> \delta$. It is also known Chebyshev norm and the infinity norm terms for this conception and notation $\left\Vert \cdot \right\Vert_\infty$. Let me say, that this is same as intention to infinity by rectangles i.e. when we require $\exists \delta_1>0, \exists \delta_2>0$ and consider $\forall n > \delta_1$ and $\forall m > \delta_2$.

Applying to big-$O$ we can write that $O(f(n,m)),(n,m) \to \infty$ is set of functions $g$, such, that $\exists C_g>0$ and $\exists M_g>0$ such that for $\forall \left\Vert (n,m)\right\Vert_\infty > M_g$ holds $g(n,m) \leqslant C_g f(n,m)$.

In your case $(2n+m)\log(2n+m) \leqslant 2(n+m)\log [2(n+m)] \leqslant 4(n+m)\log (n+m)$ using $1+\frac{\log 2}{\log (n+m)} \leqslant 2$, when $n>1,m>1$.

For completeness let me also note, that definition from one variable can be expanded to two or multi variables in different ways, for example, we can consider intention to infinity by circles i.e. when we consider $\sqrt{n^2+m^2} \to \infty$. Is known intention to infinity by triangles i.e. $n+m \to \infty $ etc.

$\endgroup$
1
$\begingroup$

The most reasonable definition for big O in several variables is: $f(n,m) = O(g(n,m))$ if there exist $n_0,m_0,C>0$ such that $f(n,m) \leq Cg(n,m)$ for all $n \geq n_0$ and $m \geq m_0$. Now you can answer your own question.

As a hint, note that $\log(2n+m) \leq \log(2n+2m) = \log 2 + \log(n+m)$.

$\endgroup$

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.