1
$\begingroup$

I have an algorithm that depends on two input sizes n and m. The complexity breaks down to the following equation:

$\frac{nm - 1}{n-1} = O(?)$

Is Big-O of the Formula $O(mn)$ or $O(m)$ because $n$ cancels out? Thank you in advance!

PS: I know that if $O(m)$ is the upper bound $O(mn)$ is an upper bound too, I want to find the tightest.

$\endgroup$
  • 2
    $\begingroup$ Landau bounds in two variables are tricky. Which one goes to infinity? Both? If so, in which way? $\endgroup$ – Raphael Aug 20 '15 at 15:10
5
$\begingroup$

I assume that $n\ge 2$, which implies $1/(n-1)\le 2/n$. Then

$$ \frac{nm-1}{n-1} \le \frac{nm}{n-1} \le 2 \frac{nm}{n} \le 2m. $$

Thus your expression is bounded by $O(m)$.

$\endgroup$
  • $\begingroup$ Thank you. Is $\frac{O(nm-1)}{O(n-1)} = \frac{O(nm)}{O(n)} = O(\frac{nm}{n}) = O(m)$ also a valid way to show this, or is that too "dirty"? $\endgroup$ – user4758246 Aug 20 '15 at 13:25
  • $\begingroup$ @user3158988: yes the $m$ was in the wrong way. The other way is indeed dirty: big-O is a set of functions - you cant divide two sets this way. $\endgroup$ – A.Schulz Aug 20 '15 at 14:50
5
$\begingroup$

Since we know nothing about the connection of $n$ and $m$ as the input size tends to infinity, we can only derive rough bounds.

Call your term

$\qquad f(n,m) = \frac{n}{n-1} \cdot m - \frac{1}{n-1}$.

Assuming $n > 1$, we have

$\qquad f(n,m) \leq 2m - \frac{1}{n-1}$

and

$\qquad f(n,m) \geq m - \frac{1}{n-1} $.

Therefore, $f(m,n) \in \Theta(m)$ as $n,m \to \infty$.

Note how very lucky you are here. It is usually not possible to get rid of one variable for such bounds without knowing how the two variables relate. In particular, make sure you understand why we can not just say "$n/(n-1) \to 1$, so $f(n,m) \sim m$".
Hint: What if $m/n \sim 1/\sqrt{n}$?

For more on asymptotics in two variables see e.g. here and here.

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