2
$\begingroup$

This is as far as i've gone: $$f(n) = \sqrt[\log n]{n} \cdot n^{\sqrt[\log n]{n}} \iff f(n)^{1 / \sqrt[\log n]{n}} = (\sqrt[\log n]{n})^{1 / \sqrt[\log n]{n} } \cdot n \iff f(n) = n^{\sqrt[\log n]{n}} $$

since $ \lim \limits_{x\to \infty} \sqrt[x]{x} = 1$

Now i haven't been able to proceed from there. If i divide $f(n)$ by $\sqrt[\log n]{n}$ i will prove that it's $\mathcal{O}\left(\sqrt[\log n]{n}\right)$ but i think i need to do better than that.. Help?

$\endgroup$
4
$\begingroup$

$$ \sqrt[\log n]{n} = n^{1/\log(n)} = \left(e^{\log(n)}\right)^{1/\log(n)} = e $$ So overall you have $f(n) = e \cdot n^e$

$\endgroup$
  • 1
    $\begingroup$ Your answers have helped me grow in strength and in wisdom. $\endgroup$ – Nikos Mar 28 '17 at 10:31
2
$\begingroup$

Observe that $$ \log\left(\sqrt[\log n]{n}\right) = \log\left(n^{1 / \log n}\right) = 1 $$

$\endgroup$
2
$\begingroup$

One may write, as $n \to \infty$, $$ f(n) = \sqrt[\log n]{n} \cdot n^{\sqrt[\log n]{n}}=n^{\large \frac1{\log n}}\cdot n^{\large n^{\frac1{\log n}}}=e^{\large \frac{\log n}{\log n}}n^{\large e^{\frac{\log n}{\log n}}}=e \cdot n^{\large e^1}\sim e \cdot n^{e}. $$

$\endgroup$
  • $\begingroup$ $f(n) = e \cdot n^e$ is true for all $n$ right? $\endgroup$ – rookie Mar 28 '17 at 10:19
  • $\begingroup$ @stud_iisc $f(n)$ is meaningless for $n=0$ and for $n=1$. As the OP asked for an order of $f(n)$, I've then considered that $n\to \infty$. $\endgroup$ – Olivier Oloa Mar 28 '17 at 12:25
  • $\begingroup$ Yes I understand that the order of $f(n)$ is what we need to find. And yeah $f(n)$ in it's original form is meaningless for $n=0$ or $1$. I just wanted to say, shouldn't the fifth similarity be just an equality? Otherwise the answer is sound. $\endgroup$ – rookie Mar 28 '17 at 14:44
  • 1
    $\begingroup$ @stud_iisc You are right! I do understand what you mean now :) $\endgroup$ – Olivier Oloa Mar 28 '17 at 19:52

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.