If $f$ is a real or complex invertible function and $f(x) = O(g(x))$ where $g$ is an invertible function, does this imply that $f^{-1}(x) = O(g^{-1}(x))$? If not in general, are there specific classes of functions, or extra restrictions under which this holds? Is there a general method of determining the asymptotic behavior of $f^{-1}$ from the asymptotic behavior of $f$?
The definition for big O notation involves absolute values, so this makes me think there could be counterexamples with certain complex valued functions or real functions at negative values, but I couldn't think of a counterexample. It's easy to come up with trivial examples of functions where this holds, but I'm not sure how to prove this in general, if it's true.
Also, if this is true, does it apply to other asymptotic relationships as well? Specifically, does this hold if we replace the big $O$ with little-$o$, $\Theta$,$\Omega$, etc.?
Best Answer
No, big O is just an asymptotic upper bound. So ln(x) is O(x), but clearly $e^x$ is not O(x). Same for $\sqrt(x)=O(x)$ yet $x^2$ is not O(x). $f(x)=O(g(x))$ is analagous to $f(x)\leq g(x)$.
The case for little o is similar. For big O we formally require $|f(x)| \leq Mg(x)$ for some M for sufficiently large x, while for little o we formally require $|f(x)| \leq \epsilon g(x)$ for all positive $\epsilon$ for sufficiently large x. Thus the examples above are also little o but not when we invert. $\Omega$ and $\omega$ are the opposite of big O and little o so the above examples hold but backwards (ie $e^x=\Omega(x)$ but ln(x) is not $\Omega(x)$).
However, you are pretty much right for $\Theta$, since it implies $f(x)$ is bounded above and below asymptotically by some multiple of $g(x)$, and if we consider visually flipping the graphs of $f$ and $g$ about $x$ it is clear that this will still hold (with the upper bound multiple being inverted to get the lower bound multiple and visa versa). In fact, this bounded above and bounded below and flipping of bounds means that for a function which is big O or $\Omega$ of another to have the inverse relationship you stipulate, it must be $\Theta$.