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

Question

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!

Why not try the same thing I mentioned in your previous question? — Simply Beautiful Art, Sep 07 '19 at 20:23

score 1 · Accepted Answer · answered Sep 07 '19 at 20:25

1

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

answered Sep 07 '19 at 20:25

ASKASK

9,000
4
28
49

So I was just that one simplification step away from the limit? I.e. $\lim_{n\to\infty} n^{\log_2(n) -b} = \infty \Rightarrow n^{\log_2 (n)} = \Omega(n^b)?$ – Peter Sep 07 '19 at 21:12
Yup, that is correct – ASKASK Sep 07 '19 at 21:13

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

1 Answers1