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.

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

2 Answers 2


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

  • $\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$ Commented Aug 20, 2015 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
    Commented Aug 20, 2015 at 14:50

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


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


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.