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?

  • $\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$ – Von Neumann 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

Your Answer

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

Browse other questions tagged or ask your own question.