Inverse function of a function involving $o(1)$

91 Views Asked by At

I am bumping into a problem when trying to write the inverse function of a function involving $o(1)$.

Here we have $t= \ln n(1+o(1))$ as $n\rightarrow \infty$

Now I want to write $n$ as a function of $t$, but I am puzzled by not knowing the rate of convergence of $o(1)$. But maybe there’s a way that I don’t need this information?

1

There are 1 best solutions below

6
On BEST ANSWER

Assuming that $t=(1+o(1))\ln n$, without knowing the rate of convergence of the $o(1)$, in this case you can still invert the $o(1)$ into another $o(1)$. For all $0<\epsilon<1$, if $n$ is bigger than some $n(\epsilon)$, then by the definition of $o(1)$ $$ (1-\epsilon)\ln n\le t\le (1+\epsilon)\ln n $$ so, exponentiating, $$ n^{1-\epsilon}\le e^t\le n^{1+\epsilon} $$ and then $$ e^{t/(1+\epsilon)}\le n\le e^{t/(1-\epsilon)}, $$ so since this is true for arbitrary $\epsilon$, $$ n=e^{t(1+o(1))}\qquad \qquad \hbox{as $n\to\infty$.} $$ Going back to $t=(1+o(1))\log n$, this statement implies that there must be some $n_0$ such that $t\le 2\log n$ for $n\ge n_0$, so, if we assume $n\ge n_0$, then $n\ge e^{t/2}$. In this case for each $n(\epsilon)$ there is a $t(\epsilon)$ so that if $t\ge t(\epsilon)$, also $n\ge n(\epsilon)$, so $n\to\infty$ as $t\to\infty$ and $$ n=e^{t(1+o(1))}\qquad \qquad \hbox{as $t\to\infty$.} $$