Prove or disprove: $n^{\log_2 n} = \Omega(n^b)$ for all $b > 0$

74 Views Asked by At

Prove or disprove: $n^{\log_2 n} = \Omega(n^b)$ for all $b > 0$

I have tried taking the limit. I know that if $\lim_{n\to\infty} \frac{f(n)}{g(n)} = \infty$ then $f(n)=\Omega(g(n))$. Is it correct to say:

$\lim_{n\to\infty} \frac{n^{\log_2 n}}{n^b}=\infty$ ?

If so, that would be an entire proof. If not, then I'm not sure how to continue working on the problem. Any help appreciated!

1

There are 1 best solutions below

2
On BEST ANSWER

$$ \frac{n^{\log_2 n}}{n^b} = n^{\log_2 n - b}$$

In expressions of the form $f(n)^{g(n)}$ where $f$ and $g$ both tend to infinity, we have that $f(n)^{g(n)}$ also tends to infinity. Do you see how that could apply here?