Equation with big O notation

Question

Recently when I read a paper on Erdos's distinct distances problem, I met the following equation $$\dfrac{(mn-x)^2}{x}=O(m^{4/3}n^{4/3}+n^2)\quad\text{where $n\ge m$},$$ and the authors immediately got $$x=\Omega(\min\{m^{2/3}n^{2/3},m^2\}).$$ But I'm wondering if there are some efficient ways to handle equations with notations such as $O$ or $\Omega$, i.e., $$f(x)=O(g(n))\text{ or }f(x)=\Omega(g(n))$$ for some given $f$ and $g$. Indeed, if $f$ is more complex than the example I gave, I think it's not enough to give an accurate bound of $x$ by a simple estimate. So could anybody recommend some detailed materials (books, papers, etc.) in this field? Thanks a lot.

Answer 1

I'd start here then head on to the external links, the further reading, and the references for that article, in that order.

For the particular step you mention, $$\frac{(mn-x)^2}{x} = x-2mn+\frac{m^{6/3}n^{6/3}}{x} \in O(m^{4/3}n^{4/3} + n^2)$$ Looking at the last fraction, which dominates this expression by having largest order, suggests pushing $x$ up to $O(m^{2/3}n^{2/3})$ won't violate the given estimate, this is $$ = k m^{2/3}n^{2/3} - 2 m n + \frac{1}{k}m^{4/3}n^{4/3}$$ for some $k$, which is clearly $O(\underline{m^{4/3}n^{4/3}} + n^2)$. Alternatively, taking $x$ to $O(m^{6/3})$ leaves $$=k m^2 - 2mn + \frac{1}{k}n^2$$ for some $k$, which is also clearly $O(m^{4/3}n^{4/3} + \underline{n^2})$. Since we can't go any further in either case, we can only push $x$ up to the lesser of the two options.

Now take a step back and notice -- in both cases the bounding term came from dividing by $x$. The apparent suppressed coefficient when comparing to the initial estimate turned out to be $1/k > 0$. This acts as a lower bound on the ratio of the two displayed equations and the big-O estimate, justifying the use of the $\Omega$.