4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Where is $Q$ defined: real numbers, integers, naturals? $\endgroup$
    – Fimpellizzeri
    Jun 16, 2017 at 15:27
  • $\begingroup$ 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 $\endgroup$
    – Brevan Ellefsen
    Jun 16, 2017 at 16:07
  • $\begingroup$ @Fimpellizieri Thank you for your comments. $Q$ is defined on integers and takes integer values. $\endgroup$
    – Dingo13
    Jun 17, 2017 at 14:06
  • $\begingroup$ My post has slightly been updated with another example. $\endgroup$
    – Dingo13
    Jun 21, 2017 at 12:31

2 Answers 2

Reset to default
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Dingo13
    Jun 17, 2017 at 14:11
  • $\begingroup$ I think that's correct. $\endgroup$
    – marty cohen
    Jun 17, 2017 at 15:40
  • $\begingroup$ Thanks for your comment. Can we prove this is correct ? $\endgroup$
    – Dingo13
    Jun 19, 2017 at 6:05
1
+100
$\begingroup$

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}$.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. Have you an idea for the other Landau notations? $\endgroup$
    – Dingo13
    Jul 5, 2017 at 11:49
  • $\begingroup$ @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. $\endgroup$
    – Alex Ravsky
    Jul 5, 2017 at 13:50
  • $\begingroup$ @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$? $\endgroup$
    – Alex Ravsky
    Jul 5, 2017 at 14:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .