Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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)$.
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.
