# Methodology searching for an asymptotic solution of an inequation

Let us suppose that we have $Q(x)$ an increasing and positive function, and we seek the (approximated) smallest $i$ such that

\begin{equation} Q(i) \geq n \end{equation}

If we can estimate $Q(i)$ using a $\Theta$ notation, can we estimate the smallest $i$ using this same Landau notation?

What about the other notations? $o$, $\sim$, ...?

Let us take an example. Suppose that $Q(i)=\Theta(f(i))$ where $f$ has an inverse $f^{−1}$. Can we say that the smallest $i$ satisfying the inequation is in $\Theta(f^{−1}(n))$ or in $O(f^{−1}(n))$ ?

Thank you.

• Where is $Q$ defined: real numbers, integers, naturals? Jun 16, 2017 at 15:27
• This depends heavily on what $Q$ is... Take, for example, $\operatorname{li}(x) - \pi(x)$ , the logarithmic integral and prime counting function. Of course, in this case our function isn't positive and increasing, so it's not a perfect example, but it goes to show how hard asymptotic analysis can be Jun 16, 2017 at 16:07
• @Fimpellizieri Thank you for your comments. $Q$ is defined on integers and takes integer values. Jun 17, 2017 at 14:06
• My post has slightly been updated with another example. Jun 21, 2017 at 12:31

This is essentially asking for the approximate inverse of $Q$.

Sometimes this is easy: If $Q(i) =i^m$ then $Q^{-1}(n) =n^{1/m}$.

Sometimes only as approximate result can be gotten: If $Q(i) = i\cdot \ln(i)$ then $Q^{-1}(n) \approx \dfrac{n}{\ln(n)}$ with additional error terms.

• Thank you for your answer. Can you say that $Q^{-1}(n) = \Theta(\frac{n}{\log n})$? Let us take another example. Suppose that $Q(i)=\Theta(f(i))$ where $f$ has an inverse $f^{-1}$. Can we say that the smallest $i$ satisfying the inequation is in $\Theta(f^{-1}(n))$ or in $O(f^{-1}(n))$ ? Thank you again Jun 17, 2017 at 14:11
• I think that's correct. Jun 17, 2017 at 15:40
• Thanks for your comment. Can we prove this is correct ? Jun 19, 2017 at 6:05

No, the claim fails even for $Q=rf+O(1)$ with a constant $r$ different from $1$. Indeed, let $f(i)=\log_2 i$. Then $f^{-1}(n)=2^n$. But if $Q(i)=\lfloor 2\log_2 i\rfloor$ then $i \simeq 2^{n/2}$, if $Q(i)=\lfloor (1/2)\log_2 i\rfloor$ then $i \simeq 2^{2n}$.

• Thank you for your answer. Have you an idea for the other Landau notations? Jul 5, 2017 at 11:49
• @Dingo13 It seems that the condition $Q=rf+O(1)$ in my counterexample implies $Q=B(f)$ for all Bachmann–Landau notations $B$ but $o$, $\omega$, and $\sim$. Maybe the cases of $o$ and $\omega$ imply only one-side bounds, but the case of $\sim$ implies two-side bounds. I’ll think about this. Jul 5, 2017 at 13:50
• @Dingo13 It seems that the claim fails even for $Q\sim f$, when $Q-f=O(1)$. I did not checked precisely the following calculation, but it looks plausible. Let $f(i)=\sqrt {\log_2 i}$. Then $f^{-1}(n)=2^{n^2}$. But if $Q(i)=\lfloor\sqrt {\log_2 i}\rfloor-2$ then $i \ge 2^{(n+1)^2}$, if $Q(i)=\lfloor\sqrt {\log_2 i}\rfloor+2$ then $i\le 2^{(n-1)^2}$. Are you interested in one-side bounds for $o$ and $\omega$? Jul 5, 2017 at 14:46