4
$\begingroup$

If $\dfrac{2^x}{\sqrt{x}}=n$ where $x\rightarrow\infty$ as $n\rightarrow\infty$, how does $x$ grow asymptotically in terms of $n$?

We know that it grows faster than $\log n$, because $\dfrac{2^{\log n}}{\sqrt{\log n}}=\dfrac{n}{\sqrt{\log n}}<n$. But it grows slower than $(\log n)^2$, because $\dfrac{2^{(\log n)^2}}{\sqrt{(\log n)^2}}=\dfrac{n^{\log n}}{\log n}>n$.

$\endgroup$
  • $\begingroup$ n(x) is not bijective therefore there is no inverted function. (at least not for n in R).... you have to at least seperate the branches (one goes to infinity the other goes to 0 which one do you want...) $\endgroup$ – Börge Oct 13 '15 at 17:56
  • $\begingroup$ @Börge Good point, edited. $\endgroup$ – Alexi Oct 13 '15 at 17:59
5
$\begingroup$

Taking logs (base 2) gives

$$ \lg n = x - \frac{\lg x}{2}, \tag{1} $$

and, dividing through by $x$,

$$ \frac{\lg n}{x} = 1 - \frac{\lg x}{2x}. $$

We observe that $x \to \infty$ as $n \to \infty$, so $(\lg x)/(2x) \to 0$ as $n \to \infty$, and thus

$$ \lim_{n \to \infty} \frac{\lg n}{x} = 1. $$

Equivalently,

$$ x \sim \lg n \qquad \text{as } n \to \infty. $$

$\endgroup$
1
$\begingroup$

Working in log to the base 2, let $y=x-\log n$ so that $y=\frac{\log x}{2}$; using that $\log n \leq x \leq 2 \log n$ (the latter bound can be applied by one more iteration of OP's argument), we get: $x-\log n - \frac{1}{2}\log \log n \in [0,c]$ for a small constant $c$.

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