0

I received an asymptotics question for my homework, which is to compare the orders of growth for $f(n)$ and $g(n)$ where:

$f(n) = n^{\log(n)}$

$g(n) = 2^n$

I have an intuition that $f(n) = O(g(n))$, and plotting the functions on a graph suggests the same thing, but I'm not sure how to tackle this. Finding $\lim \limits_{n \to \infty} \dfrac{2^n}{n^{lg(n)}}$ seems like a dead end.

Julian Kuelshammer
  • 9,670
peco
  • 111

2 Answers2

2

$\log(f(n)) = \log^2(n)$,

$\log(g(n)) = n$.

Can you compare these two?

mrp
  • 5,086
  • 2
    This doesn't always work: $n^2 = o(n^3)$ and $n^2 = O(n^3)$. After logging the second equality holds, but the first doesn't. – Alex Feb 11 '15 at 10:18
1

One more way: set $\log_2 n = t$. You get $2^{t^2}$ on LHS and $2^{2^t}$ on RHS. Now log base 2 and you get $t^2$ vs $2^t$, which is much easier.

Alex
  • 19,262