When Does n lg n Switch from Ω to O?

[Ananthan9470]

When considering the asymptotic bounds for n lgn, for what value of a in n^a does n lgn satisfy O(n^a) and for what value does it satisfy Ω(n^a)?

For example n lgn = O(n^1.261) but n lgn = Ω(n^0.797). Can someone please tell me where for what a does Ω change to O? Also how does the answer change when you consider general log_b instead of lg. Thanks!

 

[VKnopp]

A good bound that has been found for the logarithm (in a form that might be useful to you) is the following,

$\ln x \leq x^{\frac{1}{e}}$

That of course implies,

$|x \ln x| \leq |x^{\frac{e+1}{e}}|$

Now review the mathematical definition of $f(x)=O(g(x))$. You'll get the answer for your first question.

If you switch to $\log_{b} n$ you can still express it in terms of the natural logarithm and that will help you determine an asymptotic bound for logarithms with different bases.

Hope this helped.