2
$\begingroup$

I'm new to the complexity theory and have a basic question about the big-O notation that I encountered.

I came across a complexity of $O\big(\frac{n}{m-n}\big)$, where both $n$ and $m$ are independent variables in my algorithm (assuming $m \geq n$). Since I haven't encountered the subtraction of two variables in the denominator before, I'm curious if it can be simplified further, perhaps to $O\big(\frac{n}{m}\big)$ or other nicer forms. I've thought about it for some time, and maybe dividing the fraction by $n$ gives $O\big(\frac{1}{\frac{m}{n}-1}\big) = O\big(\frac{1}{\frac{m}{n}}\big) = O\big(\frac{n}{m}\big)$, but not sure if this is correct.

Additionally, I'm wondering about the whether containing expressions like $m-n$ is common or not. Any help or advice on this would be greatly appreciated :)

$\endgroup$

2 Answers 2

2
$\begingroup$

You cannot make a better conclusion in the general case:

  • if $m$ is almost $n$ (not equal to $n$, otherwise $\frac{n}0$ is not defined), then it is $\mathcal{O}(n)$;
  • if $m$ is big enough compared to $n$ (meaning $m\geqslant (1 + \varepsilon) n$, with $\varepsilon > 0$ being a constant), then it is $\mathcal{O}(1)$.

You cannot conclude that it is $\mathcal{O}\left(\frac{n}{m}\right)$ in the general case, because you neglected $1$ in front of $\frac{m}{n}$, but you cannot always do that, for example when $m = n+1$.

$\endgroup$
1
$\begingroup$

n / (m-n) is undefined for m = n. It is equal to +/- n if m = n +/- 1. But for example for m = 0 or m = 2n it is just +/- 1.

You can’t really simplify this. For fixed n, you have a function that goes from 1 to n in a hyperbola, then from -n to -1 and getting still closer to 0, also in a hyperbola. Look out if n, m are dependent of each other or if the result is used in some interesting way.

$\endgroup$

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.