0

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?

taninamdar
  • 2,618
  • 14
  • 24
  • By asymptotic behavior, do you want to find a function that is ~ to $f$? – Gregory Grant Feb 08 '16 at 21:39
  • $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!

     – Enrico M. Feb 08 '16 at 21:41
  • @GregoryGrant Yes, or if that is too strict then possible upper and lower bounds. – taninamdar Feb 08 '16 at 21:48

1 Answers1

1

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

MathRoc
  • 849