Prove whether $f(n)$ is $O$, $o$, $\Omega$, $\omega$ or $\Theta$ of $g(n)$.

30 Views Asked by At

$f(n) = e^{n} \ln(n)$, $g(n) = 2^{n} \log(n)$

log can be assumed to be base $2$.

Alright so I put this in the form $f(n) / g(n)$ and then used L'Hôpital's rule giving me

$$ \frac { \dfrac{e^n}{n} +\ln(n)e^{n} } { \dfrac{2^n}{n\ln(2)} +n2^{n-1}\log(n)} $$

and I'm pretty sure if I did this right that it's still of the form infinity/infinity and will continue to be even if I differentiate again.

I think the solution has to do something with getting the exponent of $n2^{n-1}$ to 0 by differentiating over and over. But I'm not sure how to get a solution from this.

1

There are 1 best solutions below

2
On BEST ANSWER

We can compute $$\lim_n \frac{e^n\ln n}{2^n\log n} = \lim_n \bigg[\left(\frac{e}{2}\right)^n \cdot \frac{\ln 2 \ln n}{\ln n}\bigg] = \infty.$$

Edit: To deal with the logarithms, you can use the identity $$\log_b x = \frac{\ln x}{\ln b}.$$