0
$\begingroup$

I have trouble figuring out the asymptotic behavior of two functions.

  1. If $f(n) = n \log n$, then what do we know about $f^{-1}(n)$? I.e. what is the asymptotic behavior of $g(n)$ such that $g(n) \log(g(n)) = \Theta(n)$, perhaps in terms of some familiar functions?

  2. Behavior of $n^{\frac{1}{\log \log n}}$. I know that $n^{\frac{1}{\log n}} = e$, so this function would be super-constant. But what is known about its asymptotic behavior?

$\endgroup$
3
  • $\begingroup$ By asymptotic behavior, do you want to find a function that is ~ to $f$? $\endgroup$ – Gregory Grant Feb 8 '16 at 21:39
  • $\begingroup$ $n^{\frac{1}{\ln(n)}} = e$ if and only if $n > 0$, actually. Anyway, you can always try some technique like the approximation $$\ln(n!) \approx n\ln(n) - n$$ and manipulate to see if you can pull out the rabbit! $\endgroup$ – Turing Feb 8 '16 at 21:41
  • $\begingroup$ @GregoryGrant Yes, or if that is too strict then possible upper and lower bounds. $\endgroup$ – taninamdar Feb 8 '16 at 21:48
1
$\begingroup$

You can solve these problems by iterating for several steps. To make my point clear, I'll show you an example.

Now I try to determine the large roots of the equation $$x\tan x=1,\ x>0.$$ Inversion produces $$x=n\pi+\arctan \frac{1}{x},\tag{1}$$ where $n$ is an integer and the inverse tangent has its principal value which is bounded. So $$x\sim n\pi,\ n\to \infty.$$ Next, when $x>1$, the expansion $$\arctan x^{-1}=\frac{1}{x}-\frac{1}{3x^3}+O\left(\frac{1}{x^5}\right)$$ shows that $$x-n\pi=\arctan x^{-1}=O(x^{-1})=O(n^{-1}).$$ By the formula (1), one can get \begin{align*} x& =n\pi+\frac{1}{x}+O(x^{-3})\\ & =n\pi+\frac{1}{n\pi+O(n^{-1})}+O(n^{-3})\\ & =n\pi+\frac{1}{n\pi}+O(n^{-3}). \end{align*} The next substitution produces $$x=n\pi+\frac{1}{n\pi}-\frac{4}{3\left(n\pi\right)^3}+O(n^{-3}).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.